jsonld_core/document/
expanded.rs

1use crate::{
2    HashMap,
3    Id,
4    IndexSet,
5    Indexed,
6    IndexedObject,
7    Node,
8    Object,
9    Relabel,
10    TryFromJson,
11    object::{FragmentRef, InvalidExpandedJson, Traverse},
12};
13use iri_rs::IriBuf;
14use rdfx::{
15    BlankIdBuf,
16    LocalGenerator,
17    vocabulary::{Vocabulary, VocabularyMut},
18};
19use smallvec::SmallVec;
20use std::{
21    collections::HashSet,
22    hash::{BuildHasher, Hash, Hasher},
23};
24
25/// Bucket key standing in for a full object hash.
26///
27/// Deduplicating the objects of a document needs a hash, and hashing an object
28/// walks its entire subtree — every property, every nested node. That is a
29/// steep price for what is almost always a miss.
30///
31/// This reads only the shallow fields: the kind of object, its `@index`, and,
32/// for a node, its `@id`. Equal objects necessarily agree on all three, so
33/// they always land in the same bucket, which is the property that matters.
34/// Unequal objects sharing a bucket cost nothing but the `Eq` comparison that
35/// follows.
36struct Discriminant<'a, T, B>(&'a IndexedObject<T, B>);
37
38impl<T: Hash, B: Hash> Hash for Discriminant<'_, T, B> {
39    #[inline]
40    fn hash<H: Hasher>(&self, state: &mut H) {
41        self.0.index().hash(state);
42
43        match self.0.inner() {
44            Object::Value(_) => 0u8.hash(state),
45            Object::List(_) => 1u8.hash(state),
46            Object::Node(node) => {
47                2u8.hash(state);
48                node.id.hash(state);
49            }
50        }
51    }
52}
53
54/// Result of the document expansion algorithm: a set of (indexed) objects.
55///
56/// Objects are kept in insertion order, and deduplicated through an index of
57/// discriminant buckets (shallow per-object keys) rather than by hashing
58/// each object in full.
59#[derive(Debug, Clone)]
60pub struct ExpandedDocument<T = IriBuf, B = BlankIdBuf> {
61    objects: Vec<IndexedObject<T, B>>,
62
63    /// Positions in `objects`, bucketed by discriminant. One entry inline:
64    /// collisions are the exception, not the rule.
65    buckets: HashMap<u64, SmallVec<[Entry; 1]>>,
66}
67
68/// One object's slot in a bucket.
69#[derive(Debug, Clone)]
70struct Entry {
71    /// Position in `ExpandedDocument::objects`.
72    index: usize,
73
74    /// Hash of the whole object, filled in only once this bucket holds more
75    /// than one entry.
76    ///
77    /// A bucket with a single occupant never needs it — the discriminant
78    /// already separated everything else — and computing it walks the object's
79    /// whole subtree. Documents whose objects carry distinct `@id`s therefore
80    /// never hash an object in full. Where the discriminant cannot separate
81    /// them (top-level nodes with no `@id`, say), this restores what a plain
82    /// hash set would have done: compare cheap hashes first, and reach for a
83    /// deep equality check only when they match.
84    full_hash: Option<u64>,
85}
86
87impl<T, B> Default for ExpandedDocument<T, B> {
88    #[inline(always)]
89    fn default() -> Self {
90        Self {
91            objects: Vec::new(),
92            buckets: HashMap::default(),
93        }
94    }
95}
96
97impl<T, B> ExpandedDocument<T, B> {
98    #[inline(always)]
99    /// Creates a new `ExpandedDocument`.
100    #[must_use]
101    pub fn new() -> Self {
102        Self::default()
103    }
104
105    #[inline(always)]
106    /// Creates a new `ExpandedDocument` with room for `capacity` objects.
107    ///
108    /// Worth reaching for whenever the object count is known up front: growing
109    /// the set re-hashes every object already in it, and hashing an object
110    /// walks its whole subtree.
111    #[must_use]
112    pub fn with_capacity(capacity: usize) -> Self {
113        Self {
114            objects: Vec::with_capacity(capacity),
115            buckets: HashMap::with_capacity_and_hasher(capacity, crate::hash::DefaultBuildHasher::default()),
116        }
117    }
118
119    #[inline(always)]
120    /// Returns the number of top-level objects in the document.
121    #[must_use]
122    pub fn len(&self) -> usize {
123        self.objects.len()
124    }
125
126    #[inline(always)]
127    /// Checks whether the document has no top-level objects.
128    #[must_use]
129    pub fn is_empty(&self) -> bool {
130        self.objects.is_empty()
131    }
132
133    #[inline(always)]
134    /// Returns the top-level objects of the document, in insertion order.
135    #[must_use]
136    pub fn objects(&self) -> &[IndexedObject<T, B>] {
137        &self.objects
138    }
139
140    #[inline(always)]
141    /// Consumes the document, returning its top-level objects in insertion
142    /// order.
143    #[must_use]
144    pub fn into_objects(self) -> Vec<IndexedObject<T, B>> {
145        self.objects
146    }
147
148    #[inline(always)]
149    /// Returns an iterator over the top-level objects of the document, in
150    /// insertion order.
151    pub fn iter(&self) -> std::slice::Iter<'_, IndexedObject<T, B>> {
152        self.objects.iter()
153    }
154
155    #[inline(always)]
156    /// Returns an iterator that visits every fragment of the document: each
157    /// top-level object and, recursively, everything it contains.
158    #[must_use]
159    pub fn traverse(&self) -> Traverse<'_, T, B> {
160        Traverse::new(self.iter().map(|o| FragmentRef::IndexedObject(o)))
161    }
162
163    #[inline(always)]
164    /// Counts the fragments of the document matching the given predicate.
165    pub fn count(&self, f: impl FnMut(&FragmentRef<T, B>) -> bool) -> usize {
166        self.traverse().filter(f).count()
167    }
168
169    /// Gives an identifier (`@id`) to every node, using the given generator
170    /// to create fresh identifiers for anonymous nodes.
171    ///
172    /// # Errors
173    ///
174    /// Returns an error when the generator runs out of identifiers.
175    #[inline(always)]
176    pub fn identify_all_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
177        &mut self,
178        vocabulary: &mut V,
179        generator: &mut G,
180    ) -> Result<(), crate::id::GeneratedIdError>
181    where
182        T: Eq + Hash,
183        B: Eq + Hash,
184    {
185        self.try_rewrite(|object| object.identify_all_with(vocabulary, generator))
186    }
187
188    /// Gives an identifier (`@id`) to every node, using the given generator
189    /// to create fresh identifiers for anonymous nodes.
190    ///
191    /// # Errors
192    ///
193    /// Returns an error when the generator runs out of identifiers.
194    #[inline(always)]
195    pub fn identify_all<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
196    where
197        T: Eq + Hash,
198        B: Eq + Hash,
199        (): Vocabulary<Iri = T, BlankId = B>,
200    {
201        self.identify_all_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
202    }
203
204    /// Relabels every node identifier with a fresh one from the given
205    /// generator and puts every literal into canonical form.
206    ///
207    /// # Errors
208    ///
209    /// Returns an error when the generator runs out of identifiers.
210    #[inline(always)]
211    pub fn relabel_and_canonicalize_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
212        &mut self,
213        vocabulary: &mut V,
214        generator: &mut G,
215    ) -> Result<(), crate::id::GeneratedIdError>
216    where
217        T: Clone + Eq + Hash,
218        B: Clone + Eq + Hash,
219    {
220        let mut relabeling = HashMap::default();
221        let mut buffer = ryu_js::Buffer::new();
222        self.try_rewrite(|object| {
223            object.relabel_with(vocabulary, generator, &mut relabeling)?;
224            object.canonicalize_with(&mut buffer);
225            Ok(())
226        })
227    }
228
229    /// Relabels every node identifier with a fresh one from the given
230    /// generator and puts every literal into canonical form.
231    ///
232    /// # Errors
233    ///
234    /// Returns an error when the generator runs out of identifiers.
235    #[inline(always)]
236    pub fn relabel_and_canonicalize<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
237    where
238        T: Clone + Eq + Hash,
239        B: Clone + Eq + Hash,
240        (): Vocabulary<Iri = T, BlankId = B>,
241    {
242        self.relabel_and_canonicalize_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
243    }
244
245    /// Relabels every node identifier with a fresh one from the given
246    /// generator.
247    ///
248    /// # Errors
249    ///
250    /// Returns an error when the generator runs out of identifiers.
251    #[inline(always)]
252    pub fn relabel_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
253        &mut self,
254        vocabulary: &mut V,
255        generator: &mut G,
256    ) -> Result<(), crate::id::GeneratedIdError>
257    where
258        T: Clone + Eq + Hash,
259        B: Clone + Eq + Hash,
260    {
261        let mut relabeling = HashMap::default();
262        self.try_rewrite(|object| object.relabel_with(vocabulary, generator, &mut relabeling))
263    }
264
265    /// Relabels every node identifier with a fresh one from the given
266    /// generator.
267    ///
268    /// # Errors
269    ///
270    /// Returns an error when the generator runs out of identifiers.
271    #[inline(always)]
272    pub fn relabel<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
273    where
274        T: Clone + Eq + Hash,
275        B: Clone + Eq + Hash,
276        (): Vocabulary<Iri = T, BlankId = B>,
277    {
278        self.relabel_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
279    }
280
281    /// Puts every literal of the document into canonical form, using the
282    /// given `buffer` to render numbers.
283    pub fn canonicalize_with(&mut self, buffer: &mut ryu_js::Buffer)
284    where
285        T: Eq + Hash,
286        B: Eq + Hash,
287    {
288        for mut object in self.drain() {
289            object.canonicalize_with(buffer);
290            self.insert(object);
291        }
292    }
293
294    /// Puts every literal of the document into canonical form.
295    pub fn canonicalize(&mut self)
296    where
297        T: Eq + Hash,
298        B: Eq + Hash,
299    {
300        let mut buffer = ryu_js::Buffer::new();
301        self.canonicalize_with(&mut buffer);
302    }
303
304    /// Rewrites every IRI and identifier of the document (recursively) with
305    /// the given functions.
306    pub fn map_ids<U, C>(self, mut map_iri: impl FnMut(T) -> U, mut map_id: impl FnMut(Id<T, B>) -> Id<U, C>) -> ExpandedDocument<U, C>
307    where
308        U: Eq + Hash,
309        C: Eq + Hash,
310    {
311        self.objects
312            .into_iter()
313            .map(|i| i.map_inner(|o| o.map_ids(&mut map_iri, &mut map_id)))
314            .collect()
315    }
316
317    /// Returns the set of all blank identifiers in the given document.
318    #[must_use]
319    pub fn blank_ids(&self) -> HashSet<&B>
320    where
321        B: Eq + Hash,
322    {
323        self.traverse().filter_map(|f| f.into_id().and_then(Id::into_blank)).collect()
324    }
325
326    /// Returns the main node object of the document, if any.
327    ///
328    /// The main node is the unique top level (root) node object. If multiple
329    /// node objects are on the root, `None` is returned.
330    #[must_use]
331    pub fn main_node(&self) -> Option<&Node<T, B>> {
332        let mut result = None;
333
334        for object in self {
335            if let Object::Node(node) = object.inner() {
336                if result.is_some() {
337                    return None;
338                }
339
340                result = Some(&**node);
341            }
342        }
343
344        result
345    }
346
347    /// Consumes the document and returns its main node object, if any.
348    ///
349    /// The main node is the unique top level (root) node object. If multiple
350    /// node objects are on the root, `None` is returned.
351    #[must_use]
352    pub fn into_main_node(self) -> Option<Node<T, B>> {
353        let mut result = None;
354
355        for object in self {
356            if let Object::Node(node) = object.into_inner() {
357                if result.is_some() {
358                    return None;
359                }
360
361                result = Some(*node);
362            }
363        }
364
365        result
366    }
367}
368
369impl<T: Hash + Eq, B: Hash + Eq> ExpandedDocument<T, B> {
370    /// Inserts an object, unless an equal one is already present.
371    ///
372    /// Returns `true` if the object was added.
373    pub fn insert(&mut self, object: IndexedObject<T, B>) -> bool {
374        // Cloned rather than borrowed so it stays usable while `buckets` is
375        // borrowed mutably below. A clone hashes identically to its original,
376        // which is what the cached `full_hash` values rely on.
377        let hasher = self.buckets.hasher().clone();
378        let discriminant = hasher.hash_one(Discriminant(&object));
379
380        // Split the borrow: the bucket lives in `buckets`, the candidates it
381        // points at live in `objects`.
382        let Self { objects, buckets } = self;
383        let bucket = buckets.entry(discriminant).or_default();
384
385        let full_hash = if bucket.is_empty() {
386            None
387        } else {
388            let full_hash = hasher.hash_one(&object);
389
390            for entry in bucket.iter_mut() {
391                let candidate = entry.full_hash.get_or_insert_with(|| hasher.hash_one(&objects[entry.index]));
392
393                if *candidate == full_hash && objects[entry.index] == object {
394                    return false;
395                }
396            }
397
398            Some(full_hash)
399        };
400
401        bucket.push(Entry {
402            index: objects.len(),
403            full_hash,
404        });
405        objects.push(object);
406        true
407    }
408
409    /// Checks whether an equal object is present.
410    pub fn contains(&self, object: &IndexedObject<T, B>) -> bool {
411        let discriminant = self.buckets.hasher().hash_one(Discriminant(object));
412
413        match self.buckets.get(&discriminant) {
414            Some(bucket) => bucket.iter().any(|entry| self.objects[entry.index] == *object),
415            None => false,
416        }
417    }
418
419    /// Empties the document, handing back its objects.
420    ///
421    /// Used by the passes that rewrite every object and put it back: rewriting
422    /// can make two objects equal, so the index has to be rebuilt rather than
423    /// patched.
424    fn drain(&mut self) -> std::vec::IntoIter<IndexedObject<T, B>> {
425        self.buckets.clear();
426        std::mem::take(&mut self.objects).into_iter()
427    }
428
429    /// Rewrites every object with `f`, draining and reinserting to rebuild
430    /// the index.
431    ///
432    /// If `f` fails, the failed object and the untouched remainder are
433    /// reinserted before the error is returned: the document is never
434    /// truncated on the error path (objects rewritten before the failure
435    /// keep their new form).
436    fn try_rewrite<E>(&mut self, mut f: impl FnMut(&mut IndexedObject<T, B>) -> Result<(), E>) -> Result<(), E> {
437        let mut objects = self.drain();
438        let mut result = Ok(());
439        for mut object in objects.by_ref() {
440            let object_result = f(&mut object);
441            self.insert(object);
442            if let Err(e) = object_result {
443                result = Err(e);
444                break;
445            }
446        }
447        for object in objects {
448            self.insert(object);
449        }
450        result
451    }
452}
453
454impl<T: Eq + Hash, B: Eq + Hash> From<Indexed<Node<T, B>>> for ExpandedDocument<T, B> {
455    fn from(value: Indexed<Node<T, B>>) -> Self {
456        let mut result = Self::default();
457
458        result.insert(value.map_inner(Object::node));
459
460        result
461    }
462}
463
464impl<T: Eq + Hash, B: Eq + Hash> TryFromJson<T, B> for ExpandedDocument<T, B> {
465    fn try_from_json_in(vocabulary: &mut impl VocabularyMut<Iri = T, BlankId = B>, value: jstrict::Value) -> Result<Self, InvalidExpandedJson> {
466        match value {
467            jstrict::Value::Array(items) => {
468                let mut result = Self::new();
469
470                for item in items {
471                    result.insert(Indexed::try_from_json_in(vocabulary, item)?);
472                }
473
474                Ok(result)
475            }
476            other => Err(InvalidExpandedJson::Unexpected(other.kind(), jstrict::Kind::Array)),
477        }
478    }
479}
480
481impl<T: Eq + Hash, B: Eq + Hash> PartialEq for ExpandedDocument<T, B> {
482    /// Comparison between two expanded documents.
483    ///
484    /// Order-independent, as it was when this was backed by a set: both sides
485    /// are deduplicated, so equal lengths plus containment one way is enough.
486    fn eq(&self, other: &Self) -> bool {
487        self.len() == other.len() && self.objects.iter().all(|object| other.contains(object))
488    }
489}
490
491impl<T: Eq + Hash, B: Eq + Hash> Eq for ExpandedDocument<T, B> {}
492
493impl<T, B> IntoIterator for ExpandedDocument<T, B> {
494    type IntoIter = IntoIter<T, B>;
495    type Item = IndexedObject<T, B>;
496
497    #[inline(always)]
498    fn into_iter(self) -> Self::IntoIter {
499        IntoIter(self.objects.into_iter())
500    }
501}
502
503impl<'a, T, B> IntoIterator for &'a ExpandedDocument<T, B> {
504    type IntoIter = std::slice::Iter<'a, IndexedObject<T, B>>;
505    type Item = &'a IndexedObject<T, B>;
506
507    #[inline(always)]
508    fn into_iter(self) -> Self::IntoIter {
509        self.iter()
510    }
511}
512/// Owning iterator over the objects of an expanded document.
513pub struct IntoIter<T, B>(std::vec::IntoIter<IndexedObject<T, B>>);
514
515impl<T, B> Iterator for IntoIter<T, B> {
516    type Item = IndexedObject<T, B>;
517
518    fn next(&mut self) -> Option<Self::Item> {
519        self.0.next()
520    }
521}
522
523impl<T: Hash + Eq, B: Hash + Eq> FromIterator<IndexedObject<T, B>> for ExpandedDocument<T, B> {
524    fn from_iter<I: IntoIterator<Item = IndexedObject<T, B>>>(iter: I) -> Self {
525        let iter = iter.into_iter();
526        let mut result = Self::with_capacity(iter.size_hint().0);
527        result.extend(iter);
528        result
529    }
530}
531
532impl<T: Hash + Eq, B: Hash + Eq> Extend<IndexedObject<T, B>> for ExpandedDocument<T, B> {
533    fn extend<I: IntoIterator<Item = IndexedObject<T, B>>>(&mut self, iter: I) {
534        for object in iter {
535            self.insert(object);
536        }
537    }
538}
539
540impl<T: Hash + Eq, B: Hash + Eq> From<IndexSet<IndexedObject<T, B>>> for ExpandedDocument<T, B> {
541    fn from(set: IndexSet<IndexedObject<T, B>>) -> Self {
542        set.into_iter().collect()
543    }
544}
545
546impl<T: Hash + Eq, B: Hash + Eq> From<Vec<IndexedObject<T, B>>> for ExpandedDocument<T, B> {
547    fn from(items: Vec<IndexedObject<T, B>>) -> Self {
548        items.into_iter().collect()
549    }
550}
551
552#[cfg(all(test, feature = "serde-json"))]
553// Test code may panic on failure; that is the point of a test.
554#[allow(clippy::unwrap_used, clippy::expect_used)]
555mod serde_json_tests {
556    use super::*;
557    use crate::Id;
558    use iri_rs::iri;
559
560    #[test]
561    fn expanded_into_serde_json_with_default_vocab() {
562        let id = Id::iri(IriBuf::from(iri!("https://example.com/x")));
563        let node = Node::<IriBuf, BlankIdBuf>::with_id(id);
564        let doc: ExpandedDocument<IriBuf, BlankIdBuf> = Indexed::new(node, None).into();
565
566        let json = doc.into_serde_json();
567        let arr = json.as_array().expect("expanded document is an array");
568        assert_eq!(arr.len(), 1);
569        assert_eq!(arr[0].get("@id").and_then(|v| v.as_str()), Some("https://example.com/x"));
570    }
571}
572
573// Test code may panic on failure; that is the point of a test.
574#[cfg(all(test, feature = "sonic-rs"))]
575#[allow(clippy::expect_used)]
576mod sonic_rs_tests {
577    use super::*;
578    use crate::Id;
579    use iri_rs::iri;
580    use sonic_rs::JsonValueTrait;
581
582    #[test]
583    fn expanded_into_sonic_rs_with_default_vocab() {
584        let id = Id::iri(IriBuf::from(iri!("https://example.com/x")));
585        let node = Node::<IriBuf, BlankIdBuf>::with_id(id);
586        let doc: ExpandedDocument<IriBuf, BlankIdBuf> = Indexed::new(node, None).into();
587
588        let json = doc.into_sonic_rs();
589        let arr = json.into_array().expect("expanded document is an array");
590        assert_eq!(arr.len(), 1);
591        assert_eq!(arr[0].get("@id").as_str(), Some("https://example.com/x"));
592    }
593}
594
595#[cfg(feature = "serde-json")]
596impl<T, B> ExpandedDocument<T, B> {
597    /// Converts the expanded document into a [`serde_json::Value`] using the
598    /// given `vocabulary`.
599    pub fn into_serde_json_with<N>(self, vocabulary: &N) -> serde_json::Value
600    where
601        N: Vocabulary<Iri = T, BlankId = B>,
602    {
603        use jsonld_syntax::IntoJsonWithContext;
604        self.objects.into_json_with(vocabulary).into_serde_json()
605    }
606}
607
608#[cfg(feature = "serde-json")]
609impl<T, B> ExpandedDocument<T, B>
610where
611    (): Vocabulary<Iri = T, BlankId = B>,
612{
613    /// Converts the expanded document into a [`serde_json::Value`] using the
614    /// default no-vocabulary.
615    #[must_use]
616    pub fn into_serde_json(self) -> serde_json::Value {
617        self.into_serde_json_with(rdfx::vocabulary::no_vocabulary())
618    }
619}
620
621#[cfg(feature = "sonic-rs")]
622impl<T, B> ExpandedDocument<T, B> {
623    /// Converts the expanded document into a [`sonic_rs::Value`] using the
624    /// given `vocabulary`.
625    pub fn into_sonic_rs_with<N>(self, vocabulary: &N) -> sonic_rs::Value
626    where
627        N: Vocabulary<Iri = T, BlankId = B>,
628    {
629        use jsonld_syntax::IntoJsonWithContext;
630        self.objects.into_json_with(vocabulary).into_sonic_rs()
631    }
632}
633
634#[cfg(feature = "sonic-rs")]
635impl<T, B> ExpandedDocument<T, B>
636where
637    (): Vocabulary<Iri = T, BlankId = B>,
638{
639    /// Converts the expanded document into a [`sonic_rs::Value`] using the
640    /// default no-vocabulary.
641    #[must_use]
642    pub fn into_sonic_rs(self) -> sonic_rs::Value {
643        self.into_sonic_rs_with(rdfx::vocabulary::no_vocabulary())
644    }
645}
jsonld_core/document/expanded.rs

jsonld_core/document/
expanded.rs
