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 jsonld_syntax::IntoJsonWithContext;
15use rdfx::{
16 BlankIdBuf,
17 LocalGenerator,
18 vocabulary::{Vocabulary, VocabularyMut},
19};
20use smallvec::SmallVec;
21use std::{
22 collections::HashSet,
23 hash::{BuildHasher, Hash, Hasher},
24};
25
26struct Discriminant<'a, T, B>(&'a IndexedObject<T, B>);
38
39impl<T: Hash, B: Hash> Hash for Discriminant<'_, T, B> {
40 #[inline]
41 fn hash<H: Hasher>(&self, state: &mut H) {
42 self.0.index().hash(state);
43
44 match self.0.inner() {
45 Object::Value(_) => 0u8.hash(state),
46 Object::List(_) => 1u8.hash(state),
47 Object::Node(node) => {
48 2u8.hash(state);
49 node.id.hash(state);
50 }
51 }
52 }
53}
54
55#[derive(Debug, Clone)]
61pub struct ExpandedDocument<T = IriBuf, B = BlankIdBuf> {
62 objects: Vec<IndexedObject<T, B>>,
63
64 buckets: HashMap<u64, SmallVec<[Entry; 1]>>,
67}
68
69#[derive(Debug, Clone)]
71struct Entry {
72 index: usize,
74
75 full_hash: Option<u64>,
86}
87
88impl<T, B> Default for ExpandedDocument<T, B> {
89 #[inline(always)]
90 fn default() -> Self {
91 Self {
92 objects: Vec::new(),
93 buckets: HashMap::default(),
94 }
95 }
96}
97
98impl<T, B> ExpandedDocument<T, B> {
99 #[inline(always)]
100 #[must_use]
102 pub fn new() -> Self {
103 Self::default()
104 }
105
106 #[inline(always)]
107 #[must_use]
113 pub fn with_capacity(capacity: usize) -> Self {
114 Self {
115 objects: Vec::with_capacity(capacity),
116 buckets: HashMap::with_capacity_and_hasher(capacity, crate::hash::DefaultBuildHasher::default()),
117 }
118 }
119
120 #[inline(always)]
121 #[must_use]
123 pub fn len(&self) -> usize {
124 self.objects.len()
125 }
126
127 #[inline(always)]
128 #[must_use]
130 pub fn is_empty(&self) -> bool {
131 self.objects.is_empty()
132 }
133
134 #[inline(always)]
135 #[must_use]
137 pub fn objects(&self) -> &[IndexedObject<T, B>] {
138 &self.objects
139 }
140
141 #[inline(always)]
142 #[must_use]
145 pub fn into_objects(self) -> Vec<IndexedObject<T, B>> {
146 self.objects
147 }
148
149 #[inline(always)]
150 pub fn iter(&self) -> std::slice::Iter<'_, IndexedObject<T, B>> {
153 self.objects.iter()
154 }
155
156 #[inline(always)]
157 #[must_use]
160 pub fn traverse(&self) -> Traverse<'_, T, B> {
161 Traverse::new(self.iter().map(|o| FragmentRef::IndexedObject(o)))
162 }
163
164 #[inline(always)]
165 pub fn count(&self, f: impl FnMut(&FragmentRef<T, B>) -> bool) -> usize {
167 self.traverse().filter(f).count()
168 }
169
170 #[inline(always)]
177 pub fn identify_all_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
178 &mut self,
179 vocabulary: &mut V,
180 generator: &mut G,
181 ) -> Result<(), crate::id::GeneratedIdError>
182 where
183 T: Eq + Hash,
184 B: Eq + Hash,
185 {
186 self.try_rewrite(|object| object.identify_all_with(vocabulary, generator))
187 }
188
189 #[inline(always)]
196 pub fn identify_all<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
197 where
198 T: Eq + Hash,
199 B: Eq + Hash,
200 (): Vocabulary<Iri = T, BlankId = B>,
201 {
202 self.identify_all_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
203 }
204
205 #[inline(always)]
212 pub fn relabel_and_canonicalize_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
213 &mut self,
214 vocabulary: &mut V,
215 generator: &mut G,
216 ) -> Result<(), crate::id::GeneratedIdError>
217 where
218 T: Clone + Eq + Hash,
219 B: Clone + Eq + Hash,
220 {
221 let mut relabeling = HashMap::default();
222 let mut buffer = ryu_js::Buffer::new();
223 self.try_rewrite(|object| {
224 object.relabel_with(vocabulary, generator, &mut relabeling)?;
225 object.canonicalize_with(&mut buffer);
226 Ok(())
227 })
228 }
229
230 #[inline(always)]
237 pub fn relabel_and_canonicalize<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
238 where
239 T: Clone + Eq + Hash,
240 B: Clone + Eq + Hash,
241 (): Vocabulary<Iri = T, BlankId = B>,
242 {
243 self.relabel_and_canonicalize_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
244 }
245
246 #[inline(always)]
253 pub fn relabel_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
254 &mut self,
255 vocabulary: &mut V,
256 generator: &mut G,
257 ) -> Result<(), crate::id::GeneratedIdError>
258 where
259 T: Clone + Eq + Hash,
260 B: Clone + Eq + Hash,
261 {
262 let mut relabeling = HashMap::default();
263 self.try_rewrite(|object| object.relabel_with(vocabulary, generator, &mut relabeling))
264 }
265
266 #[inline(always)]
273 pub fn relabel<G: LocalGenerator>(&mut self, generator: &mut G) -> Result<(), crate::id::GeneratedIdError>
274 where
275 T: Clone + Eq + Hash,
276 B: Clone + Eq + Hash,
277 (): Vocabulary<Iri = T, BlankId = B>,
278 {
279 self.relabel_with(rdfx::vocabulary::no_vocabulary_mut(), generator)
280 }
281
282 pub fn canonicalize_with(&mut self, buffer: &mut ryu_js::Buffer)
285 where
286 T: Eq + Hash,
287 B: Eq + Hash,
288 {
289 for mut object in self.drain() {
290 object.canonicalize_with(buffer);
291 self.insert(object);
292 }
293 }
294
295 pub fn canonicalize(&mut self)
297 where
298 T: Eq + Hash,
299 B: Eq + Hash,
300 {
301 let mut buffer = ryu_js::Buffer::new();
302 self.canonicalize_with(&mut buffer);
303 }
304
305 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>
308 where
309 U: Eq + Hash,
310 C: Eq + Hash,
311 {
312 self.objects
313 .into_iter()
314 .map(|i| i.map_inner(|o| o.map_ids(&mut map_iri, &mut map_id)))
315 .collect()
316 }
317
318 #[must_use]
320 pub fn blank_ids(&self) -> HashSet<&B>
321 where
322 B: Eq + Hash,
323 {
324 self.traverse().filter_map(|f| f.into_id().and_then(Id::into_blank)).collect()
325 }
326
327 #[must_use]
332 pub fn main_node(&self) -> Option<&Node<T, B>> {
333 let mut result = None;
334
335 for object in self {
336 if let Object::Node(node) = object.inner() {
337 if result.is_some() {
338 return None;
339 }
340
341 result = Some(&**node);
342 }
343 }
344
345 result
346 }
347
348 #[must_use]
353 pub fn into_main_node(self) -> Option<Node<T, B>> {
354 let mut result = None;
355
356 for object in self {
357 if let Object::Node(node) = object.into_inner() {
358 if result.is_some() {
359 return None;
360 }
361
362 result = Some(*node);
363 }
364 }
365
366 result
367 }
368}
369
370impl<T: Hash + Eq, B: Hash + Eq> ExpandedDocument<T, B> {
371 pub fn insert(&mut self, object: IndexedObject<T, B>) -> bool {
375 let hasher = self.buckets.hasher().clone();
379 let discriminant = hasher.hash_one(Discriminant(&object));
380
381 let Self { objects, buckets } = self;
384 let bucket = buckets.entry(discriminant).or_default();
385
386 let full_hash = if bucket.is_empty() {
387 None
388 } else {
389 let full_hash = hasher.hash_one(&object);
390
391 for entry in bucket.iter_mut() {
392 let candidate = entry.full_hash.get_or_insert_with(|| hasher.hash_one(&objects[entry.index]));
393
394 if *candidate == full_hash && objects[entry.index] == object {
395 return false;
396 }
397 }
398
399 Some(full_hash)
400 };
401
402 bucket.push(Entry {
403 index: objects.len(),
404 full_hash,
405 });
406 objects.push(object);
407 true
408 }
409
410 pub fn contains(&self, object: &IndexedObject<T, B>) -> bool {
412 let discriminant = self.buckets.hasher().hash_one(Discriminant(object));
413
414 match self.buckets.get(&discriminant) {
415 Some(bucket) => bucket.iter().any(|entry| self.objects[entry.index] == *object),
416 None => false,
417 }
418 }
419
420 fn drain(&mut self) -> std::vec::IntoIter<IndexedObject<T, B>> {
426 self.buckets.clear();
427 std::mem::take(&mut self.objects).into_iter()
428 }
429
430 fn try_rewrite<E>(&mut self, mut f: impl FnMut(&mut IndexedObject<T, B>) -> Result<(), E>) -> Result<(), E> {
438 let mut objects = self.drain();
439 let mut result = Ok(());
440 for mut object in objects.by_ref() {
441 let object_result = f(&mut object);
442 self.insert(object);
443 if let Err(e) = object_result {
444 result = Err(e);
445 break;
446 }
447 }
448 for object in objects {
449 self.insert(object);
450 }
451 result
452 }
453}
454
455impl<T: Eq + Hash, B: Eq + Hash> From<Indexed<Node<T, B>>> for ExpandedDocument<T, B> {
456 fn from(value: Indexed<Node<T, B>>) -> Self {
457 let mut result = Self::default();
458
459 result.insert(value.map_inner(Object::node));
460
461 result
462 }
463}
464
465impl<T: Eq + Hash, B: Eq + Hash> TryFromJson<T, B> for ExpandedDocument<T, B> {
466 fn try_from_json_in(vocabulary: &mut impl VocabularyMut<Iri = T, BlankId = B>, value: jstrict::Value) -> Result<Self, InvalidExpandedJson> {
467 match value {
468 jstrict::Value::Array(items) => {
469 let mut result = Self::new();
470
471 for item in items {
472 result.insert(Indexed::try_from_json_in(vocabulary, item)?);
473 }
474
475 Ok(result)
476 }
477 other => Err(InvalidExpandedJson::Unexpected(other.kind(), jstrict::Kind::Array)),
478 }
479 }
480}
481
482#[derive(Debug, thiserror::Error)]
484pub enum ExpandedJsonTextError {
485 #[error("invalid JSON: {0}")]
487 Syntax(#[from] jstrict::parse::Error),
488 #[error(transparent)]
490 Invalid(#[from] InvalidExpandedJson),
491}
492
493impl<T: Eq + Hash, B: Eq + Hash> ExpandedDocument<T, B> {
494 pub fn try_from_json_slice_in(vocabulary: &mut impl VocabularyMut<Iri = T, BlankId = B>, bytes: &[u8]) -> Result<Self, ExpandedJsonTextError> {
505 let value = jstrict::parse::parse_slice_value(bytes)?;
506 Ok(Self::try_from_json_in(vocabulary, value)?)
507 }
508}
509
510impl<T, B, N: Vocabulary<Iri = T, BlankId = B>> IntoJsonWithContext<N> for ExpandedDocument<T, B> {
511 fn into_json_with(self, vocabulary: &N) -> jstrict::Value {
515 self.objects.into_json_with(vocabulary)
516 }
517}
518
519impl<T: Eq + Hash, B: Eq + Hash> PartialEq for ExpandedDocument<T, B> {
520 fn eq(&self, other: &Self) -> bool {
525 self.len() == other.len() && self.objects.iter().all(|object| other.contains(object))
526 }
527}
528
529impl<T: Eq + Hash, B: Eq + Hash> Eq for ExpandedDocument<T, B> {}
530
531impl<T, B> IntoIterator for ExpandedDocument<T, B> {
532 type IntoIter = IntoIter<T, B>;
533 type Item = IndexedObject<T, B>;
534
535 #[inline(always)]
536 fn into_iter(self) -> Self::IntoIter {
537 IntoIter(self.objects.into_iter())
538 }
539}
540
541impl<'a, T, B> IntoIterator for &'a ExpandedDocument<T, B> {
542 type IntoIter = std::slice::Iter<'a, IndexedObject<T, B>>;
543 type Item = &'a IndexedObject<T, B>;
544
545 #[inline(always)]
546 fn into_iter(self) -> Self::IntoIter {
547 self.iter()
548 }
549}
550pub struct IntoIter<T, B>(std::vec::IntoIter<IndexedObject<T, B>>);
552
553impl<T, B> Iterator for IntoIter<T, B> {
554 type Item = IndexedObject<T, B>;
555
556 fn next(&mut self) -> Option<Self::Item> {
557 self.0.next()
558 }
559}
560
561impl<T: Hash + Eq, B: Hash + Eq> FromIterator<IndexedObject<T, B>> for ExpandedDocument<T, B> {
562 fn from_iter<I: IntoIterator<Item = IndexedObject<T, B>>>(iter: I) -> Self {
563 let iter = iter.into_iter();
564 let mut result = Self::with_capacity(iter.size_hint().0);
565 result.extend(iter);
566 result
567 }
568}
569
570impl<T: Hash + Eq, B: Hash + Eq> Extend<IndexedObject<T, B>> for ExpandedDocument<T, B> {
571 fn extend<I: IntoIterator<Item = IndexedObject<T, B>>>(&mut self, iter: I) {
572 for object in iter {
573 self.insert(object);
574 }
575 }
576}
577
578impl<T: Hash + Eq, B: Hash + Eq> From<IndexSet<IndexedObject<T, B>>> for ExpandedDocument<T, B> {
579 fn from(set: IndexSet<IndexedObject<T, B>>) -> Self {
580 set.into_iter().collect()
581 }
582}
583
584impl<T: Hash + Eq, B: Hash + Eq> From<Vec<IndexedObject<T, B>>> for ExpandedDocument<T, B> {
585 fn from(items: Vec<IndexedObject<T, B>>) -> Self {
586 items.into_iter().collect()
587 }
588}
589
590#[cfg(all(test, feature = "serde-json"))]
591#[allow(clippy::unwrap_used, clippy::expect_used)]
593mod serde_json_tests {
594 use super::*;
595 use crate::Id;
596 use iri_rs::iri;
597
598 #[test]
599 fn expanded_into_serde_json_with_default_vocab() {
600 let id = Id::iri(IriBuf::from(iri!("https://example.com/x")));
601 let node = Node::<IriBuf, BlankIdBuf>::with_id(id);
602 let doc: ExpandedDocument<IriBuf, BlankIdBuf> = Indexed::new(node, None).into();
603
604 let json = doc.into_serde_json();
605 let arr = json.as_array().expect("expanded document is an array");
606 assert_eq!(arr.len(), 1);
607 assert_eq!(arr[0].get("@id").and_then(|v| v.as_str()), Some("https://example.com/x"));
608 }
609}
610
611#[cfg(all(test, feature = "sonic-rs"))]
613#[allow(clippy::expect_used)]
614mod sonic_rs_tests {
615 use super::*;
616 use crate::Id;
617 use iri_rs::iri;
618 use sonic_rs::JsonValueTrait;
619
620 #[test]
621 fn expanded_into_sonic_rs_with_default_vocab() {
622 let id = Id::iri(IriBuf::from(iri!("https://example.com/x")));
623 let node = Node::<IriBuf, BlankIdBuf>::with_id(id);
624 let doc: ExpandedDocument<IriBuf, BlankIdBuf> = Indexed::new(node, None).into();
625
626 let json = doc.into_sonic_rs();
627 let arr = json.into_array().expect("expanded document is an array");
628 assert_eq!(arr.len(), 1);
629 assert_eq!(arr[0].get("@id").as_str(), Some("https://example.com/x"));
630 }
631}
632
633#[cfg(feature = "serde-json")]
634impl<T, B> ExpandedDocument<T, B> {
635 pub fn into_serde_json_with<N>(self, vocabulary: &N) -> serde_json::Value
638 where
639 N: Vocabulary<Iri = T, BlankId = B>,
640 {
641 self.into_json_with(vocabulary).into_serde_json()
642 }
643}
644
645#[cfg(feature = "serde-json")]
646impl<T, B> ExpandedDocument<T, B>
647where
648 (): Vocabulary<Iri = T, BlankId = B>,
649{
650 #[must_use]
653 pub fn into_serde_json(self) -> serde_json::Value {
654 self.into_serde_json_with(rdfx::vocabulary::no_vocabulary())
655 }
656}
657
658#[cfg(feature = "sonic-rs")]
659impl<T, B> ExpandedDocument<T, B> {
660 pub fn into_sonic_rs_with<N>(self, vocabulary: &N) -> sonic_rs::Value
663 where
664 N: Vocabulary<Iri = T, BlankId = B>,
665 {
666 self.into_json_with(vocabulary).into_sonic_rs()
667 }
668}
669
670#[cfg(feature = "sonic-rs")]
671impl<T, B> ExpandedDocument<T, B>
672where
673 (): Vocabulary<Iri = T, BlankId = B>,
674{
675 #[must_use]
678 pub fn into_sonic_rs(self) -> sonic_rs::Value {
679 self.into_sonic_rs_with(rdfx::vocabulary::no_vocabulary())
680 }
681}