oxrdf/
dataset.rs

1//! [In-memory implementation](Dataset) of [RDF datasets](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-dataset).
2//!
3//! Usage example:
4//! ```
5//! use oxrdf::*;
6//!
7//! let mut dataset = Dataset::default();
8//!
9//! // insertion
10//! let ex = NamedNodeRef::new("http://example.com")?;
11//! let quad = QuadRef::new(ex, ex, ex, ex);
12//! dataset.insert(quad);
13//!
14//! // simple filter
15//! let results: Vec<_> = dataset.quads_for_subject(ex).collect();
16//! assert_eq!(vec![quad], results);
17//!
18//! // direct access to a dataset graph
19//! let results: Vec<_> = dataset.graph(ex).iter().collect();
20//! assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
21//!
22//! // Print
23//! assert_eq!(
24//!     dataset.to_string(),
25//!     "<http://example.com> <http://example.com> <http://example.com> <http://example.com> .\n"
26//! );
27//! # Result::<_, Box<dyn std::error::Error>>::Ok(())
28//! ```
29//!
30//! See also [`Graph`] if you only care about plain triples.
31
32use crate::interning::*;
33use crate::*;
34#[cfg(feature = "rdfc-10")]
35use sha2::{Digest, Sha256, Sha384};
36use std::collections::hash_map::Entry;
37use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
38use std::fmt;
39use std::hash::{DefaultHasher, Hash, Hasher};
40use std::mem::take;
41
42/// An in-memory [RDF dataset](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-dataset).
43///
44/// It can accommodate a fairly large number of quads (in the few millions).
45///
46/// <div class="warning">It interns the strings and does not do any garbage collection yet:
47/// if you insert and remove a lot of different terms, memory will grow without any reduction.</div>
48///
49/// Usage example:
50/// ```
51/// use oxrdf::*;
52///
53/// let mut dataset = Dataset::default();
54///
55/// // insertion
56/// let ex = NamedNodeRef::new("http://example.com")?;
57/// let quad = QuadRef::new(ex, ex, ex, ex);
58/// dataset.insert(quad);
59///
60/// // simple filter
61/// let results: Vec<_> = dataset.quads_for_subject(ex).collect();
62/// assert_eq!(vec![quad], results);
63///
64/// // direct access to a dataset graph
65/// let results: Vec<_> = dataset.graph(ex).iter().collect();
66/// assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
67/// # Result::<_, Box<dyn std::error::Error>>::Ok(())
68/// ```
69#[derive(Debug, Default, Clone)]
70pub struct Dataset {
71    interner: Interner,
72    gspo: BTreeSet<(
73        InternedGraphName,
74        InternedNamedOrBlankNode,
75        InternedNamedNode,
76        InternedTerm,
77    )>,
78    gpos: BTreeSet<(
79        InternedGraphName,
80        InternedNamedNode,
81        InternedTerm,
82        InternedNamedOrBlankNode,
83    )>,
84    gosp: BTreeSet<(
85        InternedGraphName,
86        InternedTerm,
87        InternedNamedOrBlankNode,
88        InternedNamedNode,
89    )>,
90    spog: BTreeSet<(
91        InternedNamedOrBlankNode,
92        InternedNamedNode,
93        InternedTerm,
94        InternedGraphName,
95    )>,
96    posg: BTreeSet<(
97        InternedNamedNode,
98        InternedTerm,
99        InternedNamedOrBlankNode,
100        InternedGraphName,
101    )>,
102    ospg: BTreeSet<(
103        InternedTerm,
104        InternedNamedOrBlankNode,
105        InternedNamedNode,
106        InternedGraphName,
107    )>,
108}
109
110impl Dataset {
111    /// Creates a new dataset
112    pub fn new() -> Self {
113        Self::default()
114    }
115
116    /// Provides a read-only view on an [RDF graph](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-graph) contained in this dataset.
117    ///
118    /// ```
119    /// use oxrdf::*;
120    ///
121    /// let mut dataset = Dataset::default();
122    /// let ex = NamedNodeRef::new("http://example.com")?;
123    /// dataset.insert(QuadRef::new(ex, ex, ex, ex));
124    ///
125    /// let results: Vec<_> = dataset.graph(ex).iter().collect();
126    /// assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
127    /// # Result::<_, Box<dyn std::error::Error>>::Ok(())
128    /// ```
129    pub fn graph<'a, 'b>(&'a self, graph_name: impl Into<GraphNameRef<'b>>) -> GraphView<'a> {
130        let graph_name = self
131            .encoded_graph_name(graph_name)
132            .unwrap_or_else(InternedGraphName::impossible);
133        GraphView {
134            dataset: self,
135            graph_name,
136        }
137    }
138
139    /// Provides a read/write view on an [RDF graph](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-graph) contained in this dataset.
140    ///
141    /// ```
142    /// use oxrdf::*;
143    ///
144    /// let mut dataset = Dataset::default();
145    /// let ex = NamedNodeRef::new("http://example.com")?;
146    ///
147    /// // We edit and query the dataset http://example.com graph
148    /// {
149    ///     let mut graph = dataset.graph_mut(ex);
150    ///     graph.insert(TripleRef::new(ex, ex, ex));
151    ///     let results: Vec<_> = graph.iter().collect();
152    ///     assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
153    /// }
154    ///
155    /// // We have also changes the dataset itself
156    /// let results: Vec<_> = dataset.iter().collect();
157    /// assert_eq!(vec![QuadRef::new(ex, ex, ex, ex)], results);
158    /// # Result::<_, Box<dyn std::error::Error>>::Ok(())
159    /// ```
160    pub fn graph_mut<'a, 'b>(
161        &'a mut self,
162        graph_name: impl Into<GraphNameRef<'b>>,
163    ) -> GraphViewMut<'a> {
164        let graph_name = InternedGraphName::encoded_into(graph_name.into(), &mut self.interner);
165        GraphViewMut {
166            dataset: self,
167            graph_name,
168        }
169    }
170
171    /// Returns all the quads contained by the dataset.
172    pub fn iter(&self) -> Iter<'_> {
173        let iter = self.spog.iter();
174        Iter {
175            dataset: self,
176            inner: iter,
177        }
178    }
179
180    pub fn quads_for_subject<'a, 'b>(
181        &'a self,
182        subject: impl Into<NamedOrBlankNodeRef<'b>>,
183    ) -> impl Iterator<Item = QuadRef<'a>> + 'a {
184        let subject = self
185            .encoded_named_or_blank_node(subject)
186            .unwrap_or_else(InternedNamedOrBlankNode::impossible);
187        self.interned_quads_for_subject(&subject)
188            .map(move |q| self.decode_spog(q))
189    }
190
191    fn interned_quads_for_subject<'a>(
192        &'a self,
193        subject: &InternedNamedOrBlankNode,
194    ) -> impl Iterator<
195        Item = (
196            &'a InternedNamedOrBlankNode,
197            &'a InternedNamedNode,
198            &'a InternedTerm,
199            &'a InternedGraphName,
200        ),
201    > + use<'a> {
202        self.spog
203            .range(
204                &(
205                    *subject,
206                    InternedNamedNode::first(),
207                    InternedTerm::first(),
208                    InternedGraphName::first(),
209                )
210                    ..&(
211                        subject.next(),
212                        InternedNamedNode::first(),
213                        InternedTerm::first(),
214                        InternedGraphName::first(),
215                    ),
216            )
217            .map(|(s, p, o, g)| (s, p, o, g))
218    }
219
220    pub fn quads_for_predicate<'a, 'b>(
221        &'a self,
222        predicate: impl Into<NamedNodeRef<'b>>,
223    ) -> impl Iterator<Item = QuadRef<'a>> + 'a {
224        let predicate = self
225            .encoded_named_node(predicate)
226            .unwrap_or_else(InternedNamedNode::impossible);
227        self.interned_quads_for_predicate(predicate)
228            .map(move |q| self.decode_spog(q))
229    }
230
231    fn interned_quads_for_predicate(
232        &self,
233        predicate: InternedNamedNode,
234    ) -> impl Iterator<
235        Item = (
236            &InternedNamedOrBlankNode,
237            &InternedNamedNode,
238            &InternedTerm,
239            &InternedGraphName,
240        ),
241    > + '_ {
242        self.posg
243            .range(
244                &(
245                    predicate,
246                    InternedTerm::first(),
247                    InternedNamedOrBlankNode::first(),
248                    InternedGraphName::first(),
249                )
250                    ..&(
251                        predicate.next(),
252                        InternedTerm::first(),
253                        InternedNamedOrBlankNode::first(),
254                        InternedGraphName::first(),
255                    ),
256            )
257            .map(|(p, o, s, g)| (s, p, o, g))
258    }
259
260    pub fn quads_for_object<'a, 'b>(
261        &'a self,
262        object: impl Into<TermRef<'b>>,
263    ) -> impl Iterator<Item = QuadRef<'a>> + 'a {
264        let object = self
265            .encoded_term(object)
266            .unwrap_or_else(InternedTerm::impossible);
267
268        self.interned_quads_for_object(&object)
269            .map(move |q| self.decode_spog(q))
270    }
271
272    fn interned_quads_for_object<'a>(
273        &'a self,
274        object: &InternedTerm,
275    ) -> impl Iterator<
276        Item = (
277            &'a InternedNamedOrBlankNode,
278            &'a InternedNamedNode,
279            &'a InternedTerm,
280            &'a InternedGraphName,
281        ),
282    > + use<'a> {
283        self.ospg
284            .range(
285                &(
286                    object.clone(),
287                    InternedNamedOrBlankNode::first(),
288                    InternedNamedNode::first(),
289                    InternedGraphName::first(),
290                )
291                    ..&(
292                        object.next(),
293                        InternedNamedOrBlankNode::first(),
294                        InternedNamedNode::first(),
295                        InternedGraphName::first(),
296                    ),
297            )
298            .map(|(o, s, p, g)| (s, p, o, g))
299    }
300
301    pub fn quads_for_graph_name<'a, 'b>(
302        &'a self,
303        graph_name: impl Into<GraphNameRef<'b>>,
304    ) -> impl Iterator<Item = QuadRef<'a>> + 'a {
305        let graph_name = self
306            .encoded_graph_name(graph_name)
307            .unwrap_or_else(InternedGraphName::impossible);
308
309        self.interned_quads_for_graph_name(&graph_name)
310            .map(move |q| self.decode_spog(q))
311    }
312
313    fn interned_quads_for_graph_name<'a>(
314        &'a self,
315        graph_name: &InternedGraphName,
316    ) -> impl Iterator<
317        Item = (
318            &'a InternedNamedOrBlankNode,
319            &'a InternedNamedNode,
320            &'a InternedTerm,
321            &'a InternedGraphName,
322        ),
323    > + use<'a> {
324        self.gspo
325            .range(
326                &(
327                    *graph_name,
328                    InternedNamedOrBlankNode::first(),
329                    InternedNamedNode::first(),
330                    InternedTerm::first(),
331                )
332                    ..&(
333                        graph_name.next(),
334                        InternedNamedOrBlankNode::first(),
335                        InternedNamedNode::first(),
336                        InternedTerm::first(),
337                    ),
338            )
339            .map(|(g, s, p, o)| (s, p, o, g))
340    }
341
342    /// Retrieves quads with a filter on each quad component
343    pub fn quads_for_pattern<'a>(
344        &'a self,
345        subject: Option<NamedOrBlankNodeRef<'a>>,
346        predicate: Option<NamedNodeRef<'a>>,
347        object: Option<TermRef<'a>>,
348        graph_name: Option<GraphNameRef<'a>>,
349    ) -> impl Iterator<Item = QuadRef<'a>> + 'a {
350        let iter: Box<dyn Iterator<Item = _>> = if let Some(subject) = subject {
351            Box::new(self.quads_for_subject(subject).filter(move |q| {
352                predicate.as_ref().is_none_or(|p| *p == q.predicate)
353                    && object.as_ref().is_none_or(|o| *o == q.object)
354                    && graph_name.as_ref().is_none_or(|g| *g == q.graph_name)
355            }))
356        } else if let Some(object) = object {
357            Box::new(self.quads_for_object(object).filter(move |q| {
358                predicate.as_ref().is_none_or(|p| *p == q.predicate)
359                    && graph_name.as_ref().is_none_or(|g| *g == q.graph_name)
360            }))
361        } else if let Some(predicate) = predicate {
362            Box::new(
363                self.quads_for_predicate(predicate)
364                    .filter(move |q| graph_name.as_ref().is_none_or(|g| *g == q.graph_name)),
365            )
366        } else if let Some(graph_name) = graph_name {
367            Box::new(self.quads_for_graph_name(graph_name))
368        } else {
369            Box::new(self.iter())
370        };
371        iter
372    }
373
374    /// Checks if the dataset contains the given quad
375    pub fn contains<'a>(&self, quad: impl Into<QuadRef<'a>>) -> bool {
376        if let Some(q) = self.encoded_quad(quad.into()) {
377            self.spog.contains(&q)
378        } else {
379            false
380        }
381    }
382
383    /// Returns the number of quads in this dataset.
384    pub fn len(&self) -> usize {
385        self.gspo.len()
386    }
387
388    /// Checks if this dataset contains a quad.
389    pub fn is_empty(&self) -> bool {
390        self.gspo.is_empty()
391    }
392
393    /// Adds a quad to the dataset.
394    pub fn insert<'a>(&mut self, quad: impl Into<QuadRef<'a>>) -> bool {
395        let quad = self.encode_quad(quad.into());
396        self.insert_encoded(quad)
397    }
398
399    fn insert_encoded(
400        &mut self,
401        quad: (
402            InternedNamedOrBlankNode,
403            InternedNamedNode,
404            InternedTerm,
405            InternedGraphName,
406        ),
407    ) -> bool {
408        let (s, p, o, g) = quad;
409        self.gspo.insert((g, s, p, o.clone()));
410        self.gpos.insert((g, p, o.clone(), s));
411        self.gosp.insert((g, o.clone(), s, p));
412        self.spog.insert((s, p, o.clone(), g));
413        self.posg.insert((p, o.clone(), s, g));
414        self.ospg.insert((o, s, p, g))
415    }
416
417    /// Removes a concrete quad from the dataset.
418    pub fn remove<'a>(&mut self, quad: impl Into<QuadRef<'a>>) -> bool {
419        if let Some(quad) = self.encoded_quad(quad.into()) {
420            self.remove_encoded(quad)
421        } else {
422            false
423        }
424    }
425
426    fn remove_encoded(
427        &mut self,
428        quad: (
429            InternedNamedOrBlankNode,
430            InternedNamedNode,
431            InternedTerm,
432            InternedGraphName,
433        ),
434    ) -> bool {
435        let (s, p, o, g) = quad;
436        self.gspo.remove(&(g, s, p, o.clone()));
437        self.gpos.remove(&(g, p, o.clone(), s));
438        self.gosp.remove(&(g, o.clone(), s, p));
439        self.spog.remove(&(s, p, o.clone(), g));
440        self.posg.remove(&(p, o.clone(), s, g));
441        self.ospg.remove(&(o, s, p, g))
442    }
443
444    /// Clears the dataset.
445    pub fn clear(&mut self) {
446        self.gspo.clear();
447        self.gpos.clear();
448        self.gosp.clear();
449        self.spog.clear();
450        self.posg.clear();
451        self.ospg.clear();
452    }
453
454    fn encode_quad(
455        &mut self,
456        quad: QuadRef<'_>,
457    ) -> (
458        InternedNamedOrBlankNode,
459        InternedNamedNode,
460        InternedTerm,
461        InternedGraphName,
462    ) {
463        (
464            InternedNamedOrBlankNode::encoded_into(quad.subject, &mut self.interner),
465            InternedNamedNode::encoded_into(quad.predicate, &mut self.interner),
466            InternedTerm::encoded_into(quad.object, &mut self.interner),
467            InternedGraphName::encoded_into(quad.graph_name, &mut self.interner),
468        )
469    }
470
471    fn encoded_quad(
472        &self,
473        quad: QuadRef<'_>,
474    ) -> Option<(
475        InternedNamedOrBlankNode,
476        InternedNamedNode,
477        InternedTerm,
478        InternedGraphName,
479    )> {
480        Some((
481            self.encoded_named_or_blank_node(quad.subject)?,
482            self.encoded_named_node(quad.predicate)?,
483            self.encoded_term(quad.object)?,
484            self.encoded_graph_name(quad.graph_name)?,
485        ))
486    }
487
488    pub(super) fn encoded_named_node<'a>(
489        &self,
490        node: impl Into<NamedNodeRef<'a>>,
491    ) -> Option<InternedNamedNode> {
492        InternedNamedNode::encoded_from(node.into(), &self.interner)
493    }
494
495    pub(super) fn encoded_named_or_blank_node<'a>(
496        &self,
497        node: impl Into<NamedOrBlankNodeRef<'a>>,
498    ) -> Option<InternedNamedOrBlankNode> {
499        InternedNamedOrBlankNode::encoded_from(node.into(), &self.interner)
500    }
501
502    pub(super) fn encoded_term<'a>(&self, term: impl Into<TermRef<'a>>) -> Option<InternedTerm> {
503        InternedTerm::encoded_from(term.into(), &self.interner)
504    }
505
506    pub(super) fn encoded_graph_name<'a>(
507        &self,
508        graph_name: impl Into<GraphNameRef<'a>>,
509    ) -> Option<InternedGraphName> {
510        InternedGraphName::encoded_from(graph_name.into(), &self.interner)
511    }
512
513    fn decode_spog(
514        &self,
515        quad: (
516            &InternedNamedOrBlankNode,
517            &InternedNamedNode,
518            &InternedTerm,
519            &InternedGraphName,
520        ),
521    ) -> QuadRef<'_> {
522        QuadRef {
523            subject: quad.0.decode_from(&self.interner),
524            predicate: quad.1.decode_from(&self.interner),
525            object: quad.2.decode_from(&self.interner),
526            graph_name: quad.3.decode_from(&self.interner),
527        }
528    }
529
530    fn decode_spo(
531        &self,
532        triple: (&InternedNamedOrBlankNode, &InternedNamedNode, &InternedTerm),
533    ) -> TripleRef<'_> {
534        TripleRef {
535            subject: triple.0.decode_from(&self.interner),
536            predicate: triple.1.decode_from(&self.interner),
537            object: triple.2.decode_from(&self.interner),
538        }
539    }
540
541    /// Canonicalizes the dataset by renaming blank nodes.
542    ///
543    /// Usage example ([Dataset isomorphism](https://www.w3.org/TR/rdf11-concepts/#dfn-dataset-isomorphism)):
544    /// ```
545    /// use oxrdf::dataset::CanonicalizationAlgorithm;
546    /// use oxrdf::*;
547    ///
548    /// let iri = NamedNodeRef::new("http://example.com")?;
549    ///
550    /// let mut graph1 = Graph::new();
551    /// let bnode1 = BlankNode::default();
552    /// let g1 = BlankNode::default();
553    /// graph1.insert(QuadRef::new(iri, iri, &bnode1, &g1));
554    /// graph1.insert(QuadRef::new(&bnode1, iri, iri, &g1));
555    ///
556    /// let mut graph2 = Graph::new();
557    /// let bnode2 = BlankNode::default();
558    /// let g2 = BlankNode::default();
559    /// graph2.insert(QuadRef::new(iri, iri, &bnode2, &g2));
560    /// graph2.insert(QuadRef::new(&bnode2, iri, iri, &g2));
561    ///
562    /// assert_ne!(graph1, graph2);
563    /// graph1.canonicalize(CanonicalizationAlgorithm::Unstable);
564    /// graph2.canonicalize(CanonicalizationAlgorithm::Unstable);
565    /// assert_eq!(graph1, graph2);
566    /// # Result::<_, Box<dyn std::error::Error>>::Ok(())
567    /// ```
568    ///
569    /// It supports the [RDF Dataset Canonicalization](https://www.w3.org/TR/rdf-canon/) standard algorithm.
570    /// Support requires the `rdfc-10` feature to be enabled.
571    ///
572    /// <div class="warning">Blank node ids depend on the current shape of the graph. Adding a new quad might change the ids of a lot of blank nodes.
573    /// Hence, this canonization might not be suitable for diffs.</div>
574    ///
575    /// <div class="warning">
576    ///     This implementation's worst-case complexity is exponential with respect to the number of blank nodes in the input dataset.
577    ///     See [the RDFC specification section about it](https://www.w3.org/TR/rdf-canon/#dataset-poisoning).
578    /// </div>
579    pub fn canonicalize(&mut self, algorithm: CanonicalizationAlgorithm) {
580        let bnode_mapping = self.canonicalize_interned_blank_nodes(algorithm);
581        let new_quads = self.map_blank_nodes(&bnode_mapping);
582        self.clear();
583        for quad in new_quads {
584            self.insert_encoded(quad);
585        }
586    }
587
588    /// Returns a map between the current dataset blank node and the canonicalized blank node
589    /// to create a canonical dataset.
590    ///
591    /// See also [`canonicalize`](Self::canonicalize).
592    pub fn canonicalize_blank_nodes(
593        &self,
594        algorithm: CanonicalizationAlgorithm,
595    ) -> HashMap<BlankNodeRef<'_>, BlankNode> {
596        self.canonicalize_interned_blank_nodes(algorithm)
597            .into_iter()
598            .map(|(from, to)| (from.decode_from(&self.interner), to))
599            .collect()
600    }
601
602    fn canonicalize_interned_blank_nodes(
603        &self,
604        algorithm: CanonicalizationAlgorithm,
605    ) -> HashMap<InternedBlankNode, BlankNode> {
606        let hash_algorithm = match algorithm {
607            CanonicalizationAlgorithm::Unstable => None,
608            #[cfg(feature = "rdfc-10")]
609            CanonicalizationAlgorithm::Rdfc10 { hash_algorithm } => Some(hash_algorithm),
610        };
611        // https://www.w3.org/TR/rdf-canon/#canon-algo-algo
612        // 1)
613        let mut canonicalization_state = CanonicalizationState {
614            blank_node_to_quads_map: QuadsPerBlankNode::new(),
615            hash_to_blank_nodes_map: BTreeMap::new(),
616            canonical_issuer: IdentifierIssuer::new("c14n"),
617        };
618        // 2)
619        for quad in &self.spog {
620            if let InternedNamedOrBlankNode::BlankNode(bnode) = quad.0 {
621                Self::add_quad_to_blank_node_to_quads_map_for_blank_node(
622                    bnode,
623                    quad,
624                    &mut canonicalization_state.blank_node_to_quads_map,
625                );
626            }
627            if let InternedTerm::BlankNode(bnode) = &quad.2 {
628                Self::add_quad_to_blank_node_to_quads_map_for_blank_node(
629                    *bnode,
630                    quad,
631                    &mut canonicalization_state.blank_node_to_quads_map,
632                );
633            }
634            #[cfg(feature = "rdf-12")]
635            if let InternedTerm::Triple(t) = &quad.2 {
636                Self::add_quad_to_blank_node_to_quads_map_based_on_triple(
637                    t,
638                    quad,
639                    &mut canonicalization_state.blank_node_to_quads_map,
640                );
641            }
642            if let InternedGraphName::BlankNode(bnode) = &quad.3 {
643                Self::add_quad_to_blank_node_to_quads_map_for_blank_node(
644                    *bnode,
645                    quad,
646                    &mut canonicalization_state.blank_node_to_quads_map,
647                );
648            }
649        }
650        // 3)
651        for n in canonicalization_state.blank_node_to_quads_map.keys() {
652            // 3.1)
653            let hash = self.hash_first_degree_quads(&canonicalization_state, *n, hash_algorithm);
654            // 3.2)
655            canonicalization_state
656                .hash_to_blank_nodes_map
657                .entry(hash)
658                .or_default()
659                .push(*n);
660        }
661        // 4)
662        canonicalization_state.hash_to_blank_nodes_map = canonicalization_state
663            .hash_to_blank_nodes_map
664            .into_iter()
665            .filter(|(_, identifier_list)| {
666                match identifier_list.len() {
667                    0 => unreachable!(),
668                    // 4.1)
669                    2.. => true,
670                    1 => {
671                        // 4.2)
672                        Self::issue_identifier(
673                            &mut canonicalization_state.canonical_issuer,
674                            identifier_list[0],
675                        );
676                        // 4.3)
677                        false
678                    }
679                }
680            })
681            .collect::<BTreeMap<_, _>>();
682        // 5)
683        for (_, identifier_list) in take(&mut canonicalization_state.hash_to_blank_nodes_map) {
684            // 5.1)
685            let mut hash_path_list = Vec::new();
686            // 5.2)
687            for n in identifier_list {
688                // 5.2.1)
689                if canonicalization_state
690                    .canonical_issuer
691                    .issued_identifier_map
692                    .contains_key(&n)
693                {
694                    continue;
695                }
696                // 5.2.2)
697                let mut temporary_issuer = IdentifierIssuer::new("b");
698                // 5.2.3)
699                Self::issue_identifier(&mut temporary_issuer, n);
700                // 5.2.4)
701                hash_path_list.push(self.hash_n_degree_quads(
702                    &canonicalization_state,
703                    n,
704                    &temporary_issuer,
705                    hash_algorithm,
706                ))
707            }
708            // 5.3)
709            hash_path_list.sort_unstable_by(|(_, hl), (_, hr)| hl.cmp(hr));
710            for (result_identifier_issuer, _) in hash_path_list {
711                // 5.3.1)
712                for existing_identifier in result_identifier_issuer.issued_identifier_order {
713                    Self::issue_identifier(
714                        &mut canonicalization_state.canonical_issuer,
715                        existing_identifier,
716                    );
717                }
718            }
719        }
720        // 6)
721        canonicalization_state
722            .canonical_issuer
723            .issued_identifier_map
724    }
725
726    #[cfg(feature = "rdf-12")]
727    fn add_quad_to_blank_node_to_quads_map_based_on_triple<'a>(
728        triple: &InternedTriple,
729        quad: &'a (
730            InternedNamedOrBlankNode,
731            InternedNamedNode,
732            InternedTerm,
733            InternedGraphName,
734        ),
735        blank_node_to_quads_map: &mut QuadsPerBlankNode<'a>,
736    ) {
737        if let InternedNamedOrBlankNode::BlankNode(bnode) = triple.subject {
738            Self::add_quad_to_blank_node_to_quads_map_for_blank_node(
739                bnode,
740                quad,
741                blank_node_to_quads_map,
742            );
743        }
744        if let InternedTerm::BlankNode(bnode) = &triple.object {
745            Self::add_quad_to_blank_node_to_quads_map_for_blank_node(
746                *bnode,
747                quad,
748                blank_node_to_quads_map,
749            );
750        } else if let InternedTerm::Triple(t) = &triple.object {
751            Self::add_quad_to_blank_node_to_quads_map_based_on_triple(
752                t,
753                quad,
754                blank_node_to_quads_map,
755            );
756        }
757    }
758
759    fn add_quad_to_blank_node_to_quads_map_for_blank_node<'a>(
760        bnode: InternedBlankNode,
761        quad: &'a (
762            InternedNamedOrBlankNode,
763            InternedNamedNode,
764            InternedTerm,
765            InternedGraphName,
766        ),
767        blank_node_to_quads_map: &mut QuadsPerBlankNode<'a>,
768    ) {
769        let entry = blank_node_to_quads_map.entry(bnode).or_default();
770        if !entry.ends_with(&[quad]) {
771            entry.push(quad);
772        }
773    }
774
775    /// RDFC [Issue Identifier Algorithm](https://www.w3.org/TR/rdf-canon/#issue-identifier)
776    fn issue_identifier(issuer: &mut IdentifierIssuer, blank_node: InternedBlankNode) -> BlankNode {
777        match issuer.issued_identifier_map.entry(blank_node) {
778            // 1)
779            Entry::Occupied(entry) => entry.get().clone(),
780            Entry::Vacant(entry) => {
781                // 2)
782                let issued_identifier = BlankNode::new_unchecked(format!(
783                    "{}{}",
784                    issuer.identifier_prefix, issuer.identifier_counter
785                ));
786                // 3)
787                entry.insert(issued_identifier.clone());
788                issuer.issued_identifier_order.push(blank_node);
789                // 4)
790                issuer.identifier_counter += 1;
791                // 5)
792                issued_identifier
793            }
794        }
795    }
796
797    /// RDFC [Hash First Degree Quads](https://www.w3.org/TR/rdf-canon/#hash-1d-quads)
798    fn hash_first_degree_quads(
799        &self,
800        canonicalization_state: &CanonicalizationState<'_>,
801        reference_blank_node_identifier: InternedBlankNode,
802        hash_algorithm: Option<CanonicalizationHashAlgorithm>,
803    ) -> String {
804        // 1)
805        let mut nquads = Vec::new();
806        // 2)
807        let quads =
808            &canonicalization_state.blank_node_to_quads_map[&reference_blank_node_identifier];
809        // 3)
810        for (subject, predicate, object, graph_name) in quads {
811            // 3.1)
812            let subject = self.hash_first_degree_quads_decode_named_or_blank_node(
813                subject,
814                &reference_blank_node_identifier,
815            );
816            let predicate = predicate.decode_from(&self.interner);
817            let object =
818                self.hash_first_degree_quads_decode_term(object, &reference_blank_node_identifier);
819            let graph_name = self.hash_first_degree_quads_decode_graph_name(
820                graph_name,
821                &reference_blank_node_identifier,
822            );
823            nquads.push(if graph_name.is_default_graph() {
824                format!("{subject} {predicate} {object} .\n")
825            } else {
826                format!("{subject} {predicate} {object} {graph_name} .\n")
827            });
828        }
829        // 3)
830        nquads.sort();
831        // 4)
832        Self::hash_function(&nquads.join(""), hash_algorithm)
833    }
834
835    fn hash_first_degree_quads_decode_named_or_blank_node(
836        &self,
837        term: &InternedNamedOrBlankNode,
838        reference_blank_node_identifier: &InternedBlankNode,
839    ) -> NamedOrBlankNodeRef<'_> {
840        match term {
841            InternedNamedOrBlankNode::NamedNode(t) => t.decode_from(&self.interner).into(),
842            InternedNamedOrBlankNode::BlankNode(t) => {
843                BlankNodeRef::new_unchecked(if t == reference_blank_node_identifier {
844                    "a"
845                } else {
846                    "z"
847                })
848                .into()
849            }
850        }
851    }
852
853    fn hash_first_degree_quads_decode_term(
854        &self,
855        term: &InternedTerm,
856        reference_blank_node_identifier: &InternedBlankNode,
857    ) -> Term {
858        match term {
859            InternedTerm::NamedNode(t) => t.decode_from(&self.interner).into(),
860            InternedTerm::BlankNode(t) => {
861                BlankNodeRef::new_unchecked(if t == reference_blank_node_identifier {
862                    "a"
863                } else {
864                    "z"
865                })
866                .into()
867            }
868            InternedTerm::Literal(t) => t.decode_from(&self.interner).into(),
869            #[cfg(feature = "rdf-12")]
870            InternedTerm::Triple(t) => Triple::new(
871                self.hash_first_degree_quads_decode_named_or_blank_node(
872                    &t.subject,
873                    reference_blank_node_identifier,
874                ),
875                t.predicate.decode_from(&self.interner),
876                self.hash_first_degree_quads_decode_term(
877                    &t.object,
878                    reference_blank_node_identifier,
879                ),
880            )
881            .into(),
882        }
883    }
884
885    fn hash_first_degree_quads_decode_graph_name(
886        &self,
887        term: &InternedGraphName,
888        reference_blank_node_identifier: &InternedBlankNode,
889    ) -> GraphNameRef<'_> {
890        match term {
891            InternedGraphName::NamedNode(t) => t.decode_from(&self.interner).into(),
892            InternedGraphName::BlankNode(t) => {
893                BlankNodeRef::new_unchecked(if t == reference_blank_node_identifier {
894                    "a"
895                } else {
896                    "z"
897                })
898                .into()
899            }
900            InternedGraphName::DefaultGraph => GraphNameRef::DefaultGraph,
901        }
902    }
903
904    /// RDFC [Hash Related Blank Node](https://www.w3.org/TR/rdf-canon/#hash-related-blank-node)
905    fn hash_related_blank_node(
906        &self,
907        canonicalization_state: &CanonicalizationState<'_>,
908        related: InternedBlankNode,
909        quad: &(
910            InternedNamedOrBlankNode,
911            InternedNamedNode,
912            InternedTerm,
913            InternedGraphName,
914        ),
915        issuer: &IdentifierIssuer,
916        position: &str,
917        hash_algorithm: Option<CanonicalizationHashAlgorithm>,
918    ) -> String {
919        // 1)
920        let mut input = position.to_owned();
921        // 2)
922        if position != "g" {
923            input.push('<');
924            input.push_str(quad.1.decode_from(&self.interner).as_str());
925            input.push('>');
926        }
927        // 3)
928        if let Some(id) = canonicalization_state
929            .canonical_issuer
930            .issued_identifier_map
931            .get(&related)
932            .or_else(|| issuer.issued_identifier_map.get(&related))
933        {
934            input.push_str("_:");
935            input.push_str(id.as_str());
936        } else {
937            // 4)
938            input.push_str(&self.hash_first_degree_quads(
939                canonicalization_state,
940                related,
941                hash_algorithm,
942            ));
943        }
944        // 5)
945        Self::hash_function(&input, hash_algorithm)
946    }
947
948    /// RDFC [Hash N Degree Quads](https://www.w3.org/TR/rdf-canon/#hash-nd-quads)
949    fn hash_n_degree_quads(
950        &self,
951        canonicalization_state: &CanonicalizationState<'_>,
952        identifier: InternedBlankNode,
953        issuer: &IdentifierIssuer,
954        hash_algorithm: Option<CanonicalizationHashAlgorithm>,
955    ) -> (IdentifierIssuer, String) {
956        let mut issuer = issuer.clone();
957        // 1)
958        let mut h_n = BTreeMap::<_, HashSet<_>>::new();
959        // 2)
960        let quads = &canonicalization_state.blank_node_to_quads_map[&identifier];
961        // 3)
962        for quad in quads {
963            // 3.1)
964            if let InternedNamedOrBlankNode::BlankNode(component) = quad.0 {
965                self.hash_related_blank_node_on_possible_component(
966                    canonicalization_state,
967                    component,
968                    identifier,
969                    quad,
970                    &issuer,
971                    "s",
972                    &mut h_n,
973                    hash_algorithm,
974                );
975            }
976            if let InternedTerm::BlankNode(component) = quad.2 {
977                self.hash_related_blank_node_on_possible_component(
978                    canonicalization_state,
979                    component,
980                    identifier,
981                    quad,
982                    &issuer,
983                    "o",
984                    &mut h_n,
985                    hash_algorithm,
986                );
987            }
988            #[cfg(feature = "rdf-12")]
989            if let InternedTerm::Triple(t) = &quad.2 {
990                self.hash_related_blank_node_on_possible_triple(
991                    canonicalization_state,
992                    t,
993                    identifier,
994                    quad,
995                    &issuer,
996                    &mut h_n,
997                    hash_algorithm,
998                );
999            }
1000            if let InternedGraphName::BlankNode(component) = quad.3 {
1001                self.hash_related_blank_node_on_possible_component(
1002                    canonicalization_state,
1003                    component,
1004                    identifier,
1005                    quad,
1006                    &issuer,
1007                    "g",
1008                    &mut h_n,
1009                    hash_algorithm,
1010                );
1011            }
1012        }
1013        // 4)
1014        let mut data_to_hash = String::new();
1015        // 5)
1016        for (related_hash, blank_node_list) in h_n {
1017            // 5.1)
1018            data_to_hash.push_str(&related_hash);
1019            // 5.2)
1020            let mut chosen_path = String::new();
1021            // 5.3)
1022            let mut chosen_issuer = IdentifierIssuer::new("");
1023            // 5.4)
1024            'perm: for p in generate_permutations(blank_node_list) {
1025                // 5.4.1)
1026                let mut issuer_copy = issuer.clone();
1027                // 5.4.2)
1028                let mut path = String::new();
1029                // 5.4.3)
1030                let mut recursion_list = Vec::new();
1031                // 5.4.4)
1032                for related in p {
1033                    // 5.4.4.1)
1034                    if let Some(id) = canonicalization_state
1035                        .canonical_issuer
1036                        .issued_identifier_map
1037                        .get(&related)
1038                    {
1039                        path.push_str("_:");
1040                        path.push_str(id.as_str());
1041                    } else {
1042                        // 5.4.4.2)
1043                        // 5.4.4.2.1)
1044                        if !issuer_copy.issued_identifier_map.contains_key(&related) {
1045                            recursion_list.push(related);
1046                        }
1047                        // 5.4.4.2.2)
1048                        let id = Self::issue_identifier(&mut issuer_copy, related);
1049                        path.push_str("_:");
1050                        path.push_str(id.as_str());
1051                    }
1052                    // 5.4.4.3)
1053                    if !chosen_path.is_empty()
1054                        && path.len() >= chosen_path.len()
1055                        && path > chosen_path
1056                    {
1057                        continue 'perm;
1058                    }
1059                }
1060                // 5.4.5)
1061                for related in recursion_list {
1062                    // 5.4.5.1)
1063                    let (result_identifier_issuer, result_hash) = self.hash_n_degree_quads(
1064                        canonicalization_state,
1065                        related,
1066                        &issuer_copy,
1067                        hash_algorithm,
1068                    );
1069                    // 5.4.5.2)
1070                    let id = Self::issue_identifier(&mut issuer_copy, related);
1071                    path.push_str("_:");
1072                    path.push_str(id.as_str());
1073                    // 5.4.5.3)
1074                    path.push('<');
1075                    path.push_str(&result_hash);
1076                    path.push('>');
1077                    // 5.4.5.4)
1078                    issuer_copy = result_identifier_issuer;
1079                    // 5.4.5.5)
1080                    if !chosen_path.is_empty()
1081                        && path.len() >= chosen_path.len()
1082                        && path > chosen_path
1083                    {
1084                        continue 'perm;
1085                    }
1086                }
1087                // 5.4.6)
1088                if chosen_path.is_empty() || path < chosen_path {
1089                    chosen_path = path;
1090                    chosen_issuer = issuer_copy;
1091                }
1092            }
1093            // 5.5)
1094            data_to_hash.push_str(&chosen_path);
1095            // 5.6)
1096            issuer = chosen_issuer;
1097        }
1098        // 6)
1099        (issuer, Self::hash_function(&data_to_hash, hash_algorithm))
1100    }
1101
1102    #[cfg(feature = "rdf-12")]
1103    fn hash_related_blank_node_on_possible_triple(
1104        &self,
1105        canonicalization_state: &CanonicalizationState<'_>,
1106        triple: &InternedTriple,
1107        identifier: InternedBlankNode,
1108        quad: &(
1109            InternedNamedOrBlankNode,
1110            InternedNamedNode,
1111            InternedTerm,
1112            InternedGraphName,
1113        ),
1114        issuer: &IdentifierIssuer,
1115        h_n: &mut BTreeMap<String, HashSet<InternedBlankNode>>,
1116        hash_algorithm: Option<CanonicalizationHashAlgorithm>,
1117    ) {
1118        if let InternedNamedOrBlankNode::BlankNode(component) = triple.subject {
1119            self.hash_related_blank_node_on_possible_component(
1120                canonicalization_state,
1121                component,
1122                identifier,
1123                quad,
1124                issuer,
1125                "os",
1126                h_n,
1127                hash_algorithm,
1128            );
1129        }
1130        if let InternedTerm::BlankNode(component) = &triple.object {
1131            self.hash_related_blank_node_on_possible_component(
1132                canonicalization_state,
1133                *component,
1134                identifier,
1135                quad,
1136                issuer,
1137                "oo",
1138                h_n,
1139                hash_algorithm,
1140            );
1141        }
1142    }
1143
1144    fn hash_related_blank_node_on_possible_component(
1145        &self,
1146        canonicalization_state: &CanonicalizationState<'_>,
1147        component: InternedBlankNode,
1148        identifier: InternedBlankNode,
1149        quad: &(
1150            InternedNamedOrBlankNode,
1151            InternedNamedNode,
1152            InternedTerm,
1153            InternedGraphName,
1154        ),
1155        issuer: &IdentifierIssuer,
1156        position: &str,
1157        h_n: &mut BTreeMap<String, HashSet<InternedBlankNode>>,
1158        hash_algorithm: Option<CanonicalizationHashAlgorithm>,
1159    ) {
1160        if component != identifier {
1161            // 3.1.1)
1162            let hash = self.hash_related_blank_node(
1163                canonicalization_state,
1164                component,
1165                quad,
1166                issuer,
1167                position,
1168                hash_algorithm,
1169            );
1170            // 3.1.2)
1171            h_n.entry(hash).or_default().insert(component);
1172        }
1173    }
1174
1175    fn hash_function(input: &str, hash_algorithm: Option<CanonicalizationHashAlgorithm>) -> String {
1176        match hash_algorithm {
1177            #[cfg(feature = "rdfc-10")]
1178            Some(CanonicalizationHashAlgorithm::Sha256) => {
1179                hex::encode(Sha256::new().chain_update(input).finalize())
1180            }
1181            #[cfg(feature = "rdfc-10")]
1182            Some(CanonicalizationHashAlgorithm::Sha384) => {
1183                hex::encode(Sha384::new().chain_update(input).finalize())
1184            }
1185            None => {
1186                let mut hasher = DefaultHasher::new();
1187                input.hash(&mut hasher);
1188                hasher.finish().to_string()
1189            }
1190        }
1191    }
1192
1193    #[expect(clippy::needless_collect)]
1194    fn map_blank_nodes(
1195        &mut self,
1196        bnode_mapping: &HashMap<InternedBlankNode, BlankNode>,
1197    ) -> Vec<(
1198        InternedNamedOrBlankNode,
1199        InternedNamedNode,
1200        InternedTerm,
1201        InternedGraphName,
1202    )> {
1203        let old_quads: Vec<_> = self.spog.iter().cloned().collect();
1204        old_quads
1205            .into_iter()
1206            .map(|(s, p, o, g)| {
1207                (
1208                    match s {
1209                        InternedNamedOrBlankNode::NamedNode(_) => s,
1210                        InternedNamedOrBlankNode::BlankNode(bnode) => {
1211                            InternedNamedOrBlankNode::BlankNode(InternedBlankNode::encoded_into(
1212                                bnode_mapping[&bnode].as_ref(),
1213                                &mut self.interner,
1214                            ))
1215                        }
1216                    },
1217                    p,
1218                    match o {
1219                        InternedTerm::NamedNode(_) | InternedTerm::Literal(_) => o,
1220                        InternedTerm::BlankNode(bnode) => {
1221                            InternedTerm::BlankNode(InternedBlankNode::encoded_into(
1222                                bnode_mapping[&bnode].as_ref(),
1223                                &mut self.interner,
1224                            ))
1225                        }
1226                        #[cfg(feature = "rdf-12")]
1227                        InternedTerm::Triple(triple) => {
1228                            InternedTerm::Triple(Box::new(InternedTriple::encoded_into(
1229                                self.map_triple_blank_nodes(&triple, bnode_mapping).as_ref(),
1230                                &mut self.interner,
1231                            )))
1232                        }
1233                    },
1234                    match g {
1235                        InternedGraphName::NamedNode(_) | InternedGraphName::DefaultGraph => g,
1236                        InternedGraphName::BlankNode(bnode) => {
1237                            InternedGraphName::BlankNode(InternedBlankNode::encoded_into(
1238                                bnode_mapping[&bnode].as_ref(),
1239                                &mut self.interner,
1240                            ))
1241                        }
1242                    },
1243                )
1244            })
1245            .collect()
1246    }
1247
1248    #[cfg(feature = "rdf-12")]
1249    fn map_triple_blank_nodes(
1250        &mut self,
1251        triple: &InternedTriple,
1252        bnode_mapping: &HashMap<InternedBlankNode, BlankNode>,
1253    ) -> Triple {
1254        Triple {
1255            subject: if let InternedNamedOrBlankNode::BlankNode(bnode) = &triple.subject {
1256                bnode_mapping[bnode].clone().into()
1257            } else {
1258                triple.subject.decode_from(&self.interner).into_owned()
1259            },
1260            predicate: triple.predicate.decode_from(&self.interner).into_owned(),
1261            object: if let InternedTerm::BlankNode(bnode) = &triple.object {
1262                bnode_mapping[bnode].clone().into()
1263            } else if let InternedTerm::Triple(t) = &triple.object {
1264                self.map_triple_blank_nodes(t, bnode_mapping).into()
1265            } else {
1266                triple.object.decode_from(&self.interner).into_owned()
1267            },
1268        }
1269    }
1270}
1271
1272impl PartialEq for Dataset {
1273    fn eq(&self, other: &Self) -> bool {
1274        if self.len() != other.len() {
1275            return false;
1276        }
1277        for q in self {
1278            if !other.contains(q) {
1279                return false;
1280            }
1281        }
1282        true
1283    }
1284}
1285
1286impl Eq for Dataset {}
1287
1288impl<'a> IntoIterator for &'a Dataset {
1289    type Item = QuadRef<'a>;
1290    type IntoIter = Iter<'a>;
1291
1292    fn into_iter(self) -> Self::IntoIter {
1293        self.iter()
1294    }
1295}
1296
1297impl FromIterator<Quad> for Dataset {
1298    fn from_iter<I: IntoIterator<Item = Quad>>(iter: I) -> Self {
1299        let mut g = Self::new();
1300        g.extend(iter);
1301        g
1302    }
1303}
1304
1305impl<'a, T: Into<QuadRef<'a>>> FromIterator<T> for Dataset {
1306    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1307        let mut g = Self::new();
1308        g.extend(iter);
1309        g
1310    }
1311}
1312
1313impl Extend<Quad> for Dataset {
1314    fn extend<I: IntoIterator<Item = Quad>>(&mut self, iter: I) {
1315        for t in iter {
1316            self.insert(&t);
1317        }
1318    }
1319}
1320
1321impl<'a, T: Into<QuadRef<'a>>> Extend<T> for Dataset {
1322    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1323        for t in iter {
1324            self.insert(t);
1325        }
1326    }
1327}
1328
1329impl fmt::Display for Dataset {
1330    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1331        for t in self {
1332            writeln!(f, "{t} .")?;
1333        }
1334        Ok(())
1335    }
1336}
1337
1338/// A read-only view on an [RDF graph](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-graph) contained in a [`Dataset`].
1339///
1340/// It is built using the [`Dataset::graph`] method.
1341///
1342/// Usage example:
1343/// ```
1344/// use oxrdf::*;
1345///
1346/// let mut dataset = Dataset::default();
1347/// let ex = NamedNodeRef::new("http://example.com")?;
1348/// dataset.insert(QuadRef::new(ex, ex, ex, ex));
1349///
1350/// let results: Vec<_> = dataset.graph(ex).iter().collect();
1351/// assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
1352/// # Result::<_, Box<dyn std::error::Error>>::Ok(())
1353/// ```
1354#[derive(Clone, Debug)]
1355pub struct GraphView<'a> {
1356    dataset: &'a Dataset,
1357    graph_name: InternedGraphName,
1358}
1359
1360impl<'a> GraphView<'a> {
1361    /// Returns all the triples contained by the graph.
1362    pub fn iter(&self) -> GraphViewIter<'a> {
1363        let iter = self.dataset.gspo.range(
1364            &(
1365                self.graph_name,
1366                InternedNamedOrBlankNode::first(),
1367                InternedNamedNode::first(),
1368                InternedTerm::first(),
1369            )
1370                ..&(
1371                    self.graph_name.next(),
1372                    InternedNamedOrBlankNode::first(),
1373                    InternedNamedNode::first(),
1374                    InternedTerm::first(),
1375                ),
1376        );
1377        GraphViewIter {
1378            dataset: self.dataset,
1379            inner: iter,
1380        }
1381    }
1382
1383    pub fn triples_for_subject<'b>(
1384        &self,
1385        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1386    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1387        self.triples_for_interned_subject(self.dataset.encoded_named_or_blank_node(subject))
1388    }
1389
1390    pub(super) fn triples_for_interned_subject(
1391        &self,
1392        subject: Option<InternedNamedOrBlankNode>,
1393    ) -> impl Iterator<Item = TripleRef<'a>> + use<'a> {
1394        let subject = subject.unwrap_or_else(InternedNamedOrBlankNode::impossible);
1395        let ds = self.dataset;
1396        self.dataset
1397            .gspo
1398            .range(
1399                &(
1400                    self.graph_name,
1401                    subject,
1402                    InternedNamedNode::first(),
1403                    InternedTerm::first(),
1404                )
1405                    ..&(
1406                        self.graph_name,
1407                        subject.next(),
1408                        InternedNamedNode::first(),
1409                        InternedTerm::first(),
1410                    ),
1411            )
1412            .map(move |q| {
1413                let (_, s, p, o) = q;
1414                ds.decode_spo((s, p, o))
1415            })
1416    }
1417
1418    pub fn objects_for_subject_predicate<'b>(
1419        &self,
1420        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1421        predicate: impl Into<NamedNodeRef<'b>>,
1422    ) -> impl Iterator<Item = TermRef<'a>> + 'a {
1423        self.objects_for_interned_subject_predicate(
1424            self.dataset.encoded_named_or_blank_node(subject),
1425            self.dataset.encoded_named_node(predicate),
1426        )
1427    }
1428
1429    pub(super) fn objects_for_interned_subject_predicate(
1430        &self,
1431        subject: Option<InternedNamedOrBlankNode>,
1432        predicate: Option<InternedNamedNode>,
1433    ) -> impl Iterator<Item = TermRef<'a>> + use<'a> {
1434        let subject = subject.unwrap_or_else(InternedNamedOrBlankNode::impossible);
1435        let predicate = predicate.unwrap_or_else(InternedNamedNode::impossible);
1436        let ds = self.dataset;
1437        self.dataset
1438            .gspo
1439            .range(
1440                &(self.graph_name, subject, predicate, InternedTerm::first())
1441                    ..&(
1442                        self.graph_name,
1443                        subject,
1444                        predicate.next(),
1445                        InternedTerm::first(),
1446                    ),
1447            )
1448            .map(move |q| q.3.decode_from(&ds.interner))
1449    }
1450
1451    pub fn object_for_subject_predicate<'b>(
1452        &self,
1453        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1454        predicate: impl Into<NamedNodeRef<'b>>,
1455    ) -> Option<TermRef<'a>> {
1456        self.objects_for_subject_predicate(subject, predicate)
1457            .next()
1458    }
1459
1460    pub fn predicates_for_subject_object<'b>(
1461        &self,
1462        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1463        object: impl Into<TermRef<'b>>,
1464    ) -> impl Iterator<Item = NamedNodeRef<'a>> + 'a {
1465        self.predicates_for_interned_subject_object(
1466            self.dataset.encoded_named_or_blank_node(subject),
1467            self.dataset.encoded_term(object),
1468        )
1469    }
1470
1471    pub(super) fn predicates_for_interned_subject_object(
1472        &self,
1473        subject: Option<InternedNamedOrBlankNode>,
1474        object: Option<InternedTerm>,
1475    ) -> impl Iterator<Item = NamedNodeRef<'a>> + use<'a> {
1476        let subject = subject.unwrap_or_else(InternedNamedOrBlankNode::impossible);
1477        let object = object.unwrap_or_else(InternedTerm::impossible);
1478        let ds = self.dataset;
1479        self.dataset
1480            .gosp
1481            .range(
1482                &(
1483                    self.graph_name,
1484                    object.clone(),
1485                    subject,
1486                    InternedNamedNode::first(),
1487                )
1488                    ..&(
1489                        self.graph_name,
1490                        object,
1491                        subject.next(),
1492                        InternedNamedNode::first(),
1493                    ),
1494            )
1495            .map(move |q| q.3.decode_from(&ds.interner))
1496    }
1497
1498    pub fn triples_for_predicate<'b>(
1499        &self,
1500        predicate: impl Into<NamedNodeRef<'b>>,
1501    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1502        self.triples_for_interned_predicate(self.dataset.encoded_named_node(predicate))
1503    }
1504
1505    pub(super) fn triples_for_interned_predicate(
1506        &self,
1507        predicate: Option<InternedNamedNode>,
1508    ) -> impl Iterator<Item = TripleRef<'a>> + use<'a> {
1509        let predicate = predicate.unwrap_or_else(InternedNamedNode::impossible);
1510        let ds = self.dataset;
1511        self.dataset
1512            .gpos
1513            .range(
1514                &(
1515                    self.graph_name,
1516                    predicate,
1517                    InternedTerm::first(),
1518                    InternedNamedOrBlankNode::first(),
1519                )
1520                    ..&(
1521                        self.graph_name,
1522                        predicate.next(),
1523                        InternedTerm::first(),
1524                        InternedNamedOrBlankNode::first(),
1525                    ),
1526            )
1527            .map(move |(_, p, o, s)| ds.decode_spo((s, p, o)))
1528    }
1529
1530    pub fn subjects_for_predicate_object<'b>(
1531        &self,
1532        predicate: impl Into<NamedNodeRef<'b>>,
1533        object: impl Into<TermRef<'b>>,
1534    ) -> impl Iterator<Item = NamedOrBlankNodeRef<'a>> + 'a {
1535        self.subjects_for_interned_predicate_object(
1536            self.dataset.encoded_named_node(predicate),
1537            self.dataset.encoded_term(object),
1538        )
1539    }
1540
1541    pub(super) fn subjects_for_interned_predicate_object(
1542        &self,
1543        predicate: Option<InternedNamedNode>,
1544        object: Option<InternedTerm>,
1545    ) -> impl Iterator<Item = NamedOrBlankNodeRef<'a>> + use<'a> {
1546        let predicate = predicate.unwrap_or_else(InternedNamedNode::impossible);
1547        let object = object.unwrap_or_else(InternedTerm::impossible);
1548        let ds = self.dataset;
1549        self.dataset
1550            .gpos
1551            .range(
1552                &(
1553                    self.graph_name,
1554                    predicate,
1555                    object.clone(),
1556                    InternedNamedOrBlankNode::first(),
1557                )
1558                    ..&(
1559                        self.graph_name,
1560                        predicate,
1561                        object.next(),
1562                        InternedNamedOrBlankNode::first(),
1563                    ),
1564            )
1565            .map(move |q| q.3.decode_from(&ds.interner))
1566    }
1567
1568    pub fn subject_for_predicate_object<'b>(
1569        &self,
1570        predicate: impl Into<NamedNodeRef<'b>>,
1571        object: impl Into<TermRef<'b>>,
1572    ) -> Option<NamedOrBlankNodeRef<'a>> {
1573        self.subjects_for_predicate_object(predicate, object).next()
1574    }
1575
1576    pub fn triples_for_object<'b>(
1577        &self,
1578        object: impl Into<TermRef<'b>>,
1579    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1580        self.triples_for_interned_object(self.dataset.encoded_term(object))
1581    }
1582
1583    pub(super) fn triples_for_interned_object(
1584        &self,
1585        object: Option<InternedTerm>,
1586    ) -> impl Iterator<Item = TripleRef<'a>> + use<'a> {
1587        let object = object.unwrap_or_else(InternedTerm::impossible);
1588        let ds = self.dataset;
1589        self.dataset
1590            .gosp
1591            .range(
1592                &(
1593                    self.graph_name,
1594                    object.clone(),
1595                    InternedNamedOrBlankNode::first(),
1596                    InternedNamedNode::first(),
1597                )
1598                    ..&(
1599                        self.graph_name,
1600                        object.next(),
1601                        InternedNamedOrBlankNode::first(),
1602                        InternedNamedNode::first(),
1603                    ),
1604            )
1605            .map(move |(_, o, s, p)| ds.decode_spo((s, p, o)))
1606    }
1607
1608    /// Retrieves triples with a filter on each triple component
1609    pub fn triples_for_pattern(
1610        &self,
1611        subject: Option<NamedOrBlankNodeRef<'a>>,
1612        predicate: Option<NamedNodeRef<'a>>,
1613        object: Option<TermRef<'a>>,
1614    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1615        let iter: Box<dyn Iterator<Item = _>> = match (subject, predicate, object) {
1616            (Some(subject), Some(predicate), Some(object)) => {
1617                let triple = TripleRef::new(subject, predicate, object);
1618                Box::new(self.contains(triple).then_some(triple).into_iter())
1619            }
1620            (Some(subject), Some(predicate), None) => Box::new(
1621                self.objects_for_subject_predicate(subject, predicate)
1622                    .map(move |object| TripleRef::new(subject, predicate, object)),
1623            ),
1624            (Some(subject), None, Some(object)) => Box::new(
1625                self.predicates_for_subject_object(subject, object)
1626                    .map(move |predicate| TripleRef::new(subject, predicate, object)),
1627            ),
1628            (Some(subject), None, None) => Box::new(self.triples_for_subject(subject)),
1629            (None, Some(predicate), Some(object)) => Box::new(
1630                self.subjects_for_predicate_object(predicate, object)
1631                    .map(move |subject| TripleRef::new(subject, predicate, object)),
1632            ),
1633            (None, Some(predicate), None) => Box::new(self.triples_for_predicate(predicate)),
1634            (None, None, Some(object)) => Box::new(self.triples_for_object(object)),
1635            (None, None, None) => Box::new(self.iter()),
1636        };
1637        iter
1638    }
1639
1640    /// Checks if the graph contains the given triple.
1641    pub fn contains<'b>(&self, triple: impl Into<TripleRef<'b>>) -> bool {
1642        if let Some(triple) = self.encoded_triple(triple.into()) {
1643            self.dataset.gspo.contains(&(
1644                self.graph_name,
1645                triple.subject,
1646                triple.predicate,
1647                triple.object,
1648            ))
1649        } else {
1650            false
1651        }
1652    }
1653
1654    /// Returns the number of triples in this graph.
1655    pub fn len(&self) -> usize {
1656        self.iter().count()
1657    }
1658
1659    /// Checks if this graph contains a triple.
1660    pub fn is_empty(&self) -> bool {
1661        self.iter().next().is_none()
1662    }
1663
1664    fn encoded_triple(&self, triple: TripleRef<'_>) -> Option<InternedTriple> {
1665        Some(InternedTriple {
1666            subject: self.dataset.encoded_named_or_blank_node(triple.subject)?,
1667            predicate: self.dataset.encoded_named_node(triple.predicate)?,
1668            object: self.dataset.encoded_term(triple.object)?,
1669        })
1670    }
1671}
1672
1673impl<'a> IntoIterator for GraphView<'a> {
1674    type Item = TripleRef<'a>;
1675    type IntoIter = GraphViewIter<'a>;
1676
1677    fn into_iter(self) -> Self::IntoIter {
1678        self.iter()
1679    }
1680}
1681
1682impl<'a> IntoIterator for &GraphView<'a> {
1683    type Item = TripleRef<'a>;
1684    type IntoIter = GraphViewIter<'a>;
1685
1686    fn into_iter(self) -> Self::IntoIter {
1687        self.iter()
1688    }
1689}
1690
1691impl fmt::Display for GraphView<'_> {
1692    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1693        for t in self {
1694            writeln!(f, "{t} .")?;
1695        }
1696        Ok(())
1697    }
1698}
1699
1700/// A read/write view on an [RDF graph](https://www.w3.org/TR/rdf11-concepts/#dfn-rdf-graph) contained in a [`Dataset`].
1701///
1702/// It is built using the [`Dataset::graph_mut`] method.
1703///
1704/// Usage example:
1705/// ```
1706/// use oxrdf::*;
1707///
1708/// let mut dataset = Dataset::default();
1709/// let ex = NamedNodeRef::new("http://example.com")?;
1710///
1711/// // We edit and query the dataset http://example.com graph
1712/// {
1713///     let mut graph = dataset.graph_mut(ex);
1714///     graph.insert(TripleRef::new(ex, ex, ex));
1715///     let results: Vec<_> = graph.iter().collect();
1716///     assert_eq!(vec![TripleRef::new(ex, ex, ex)], results);
1717/// }
1718///
1719/// // We have also changes the dataset itself
1720/// let results: Vec<_> = dataset.iter().collect();
1721/// assert_eq!(vec![QuadRef::new(ex, ex, ex, ex)], results);
1722/// # Result::<_, Box<dyn std::error::Error>>::Ok(())
1723/// ```
1724#[derive(Debug)]
1725pub struct GraphViewMut<'a> {
1726    dataset: &'a mut Dataset,
1727    graph_name: InternedGraphName,
1728}
1729
1730impl<'a> GraphViewMut<'a> {
1731    fn read(&self) -> GraphView<'_> {
1732        GraphView {
1733            dataset: self.dataset,
1734            graph_name: self.graph_name,
1735        }
1736    }
1737
1738    /// Adds a triple to the graph.
1739    pub fn insert<'b>(&mut self, triple: impl Into<TripleRef<'b>>) -> bool {
1740        let triple = self.encode_triple(triple.into());
1741        self.dataset.insert_encoded((
1742            triple.subject,
1743            triple.predicate,
1744            triple.object,
1745            self.graph_name,
1746        ))
1747    }
1748
1749    /// Removes a concrete triple from the graph.
1750    pub fn remove<'b>(&mut self, triple: impl Into<TripleRef<'b>>) -> bool {
1751        if let Some(triple) = self.read().encoded_triple(triple.into()) {
1752            self.dataset.remove_encoded((
1753                triple.subject,
1754                triple.predicate,
1755                triple.object,
1756                self.graph_name,
1757            ))
1758        } else {
1759            false
1760        }
1761    }
1762
1763    fn encode_triple(&mut self, triple: TripleRef<'_>) -> InternedTriple {
1764        InternedTriple {
1765            subject: InternedNamedOrBlankNode::encoded_into(
1766                triple.subject,
1767                &mut self.dataset.interner,
1768            ),
1769            predicate: InternedNamedNode::encoded_into(
1770                triple.predicate,
1771                &mut self.dataset.interner,
1772            ),
1773            object: InternedTerm::encoded_into(triple.object, &mut self.dataset.interner),
1774        }
1775    }
1776
1777    /// Returns all the triples contained by the graph
1778    pub fn iter(&'a self) -> GraphViewIter<'a> {
1779        self.read().iter()
1780    }
1781
1782    pub fn triples_for_subject<'b>(
1783        &'a self,
1784        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1785    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1786        self.read()
1787            .triples_for_interned_subject(self.dataset.encoded_named_or_blank_node(subject))
1788    }
1789
1790    pub fn objects_for_subject_predicate<'b>(
1791        &'a self,
1792        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1793        predicate: impl Into<NamedNodeRef<'b>>,
1794    ) -> impl Iterator<Item = TermRef<'a>> + 'a {
1795        self.read().objects_for_interned_subject_predicate(
1796            self.dataset.encoded_named_or_blank_node(subject),
1797            self.dataset.encoded_named_node(predicate),
1798        )
1799    }
1800
1801    pub fn object_for_subject_predicate<'b>(
1802        &'a self,
1803        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1804        predicate: impl Into<NamedNodeRef<'b>>,
1805    ) -> Option<TermRef<'a>> {
1806        self.read().object_for_subject_predicate(subject, predicate)
1807    }
1808
1809    pub fn predicates_for_subject_object<'b>(
1810        &'a self,
1811        subject: impl Into<NamedOrBlankNodeRef<'b>>,
1812        object: impl Into<TermRef<'b>>,
1813    ) -> impl Iterator<Item = NamedNodeRef<'a>> + 'a {
1814        self.read().predicates_for_interned_subject_object(
1815            self.dataset.encoded_named_or_blank_node(subject),
1816            self.dataset.encoded_term(object),
1817        )
1818    }
1819
1820    pub fn triples_for_predicate<'b>(
1821        &'a self,
1822        predicate: impl Into<NamedNodeRef<'b>>,
1823    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1824        self.read()
1825            .triples_for_interned_predicate(self.dataset.encoded_named_node(predicate))
1826    }
1827
1828    pub fn subjects_for_predicate_object<'b>(
1829        &'a self,
1830        predicate: impl Into<NamedNodeRef<'b>>,
1831        object: impl Into<TermRef<'b>>,
1832    ) -> impl Iterator<Item = NamedOrBlankNodeRef<'a>> + 'a {
1833        self.read().subjects_for_interned_predicate_object(
1834            self.dataset.encoded_named_node(predicate),
1835            self.dataset.encoded_term(object),
1836        )
1837    }
1838
1839    pub fn subject_for_predicate_object<'b>(
1840        &'a self,
1841        predicate: impl Into<NamedNodeRef<'b>>,
1842        object: impl Into<TermRef<'b>>,
1843    ) -> Option<NamedOrBlankNodeRef<'a>> {
1844        self.read().subject_for_predicate_object(predicate, object)
1845    }
1846
1847    pub fn triples_for_object<'b>(
1848        &'a self,
1849        object: TermRef<'b>,
1850    ) -> impl Iterator<Item = TripleRef<'a>> + 'a {
1851        self.read()
1852            .triples_for_interned_object(self.dataset.encoded_term(object))
1853    }
1854
1855    /// Checks if the graph contains the given triple.
1856    pub fn contains<'b>(&self, triple: impl Into<TripleRef<'b>>) -> bool {
1857        self.read().contains(triple)
1858    }
1859
1860    /// Returns the number of triples in this graph.
1861    pub fn len(&self) -> usize {
1862        self.read().len()
1863    }
1864
1865    /// Checks if this graph contains a triple.
1866    pub fn is_empty(&self) -> bool {
1867        self.read().is_empty()
1868    }
1869}
1870
1871impl Extend<Triple> for GraphViewMut<'_> {
1872    fn extend<I: IntoIterator<Item = Triple>>(&mut self, iter: I) {
1873        for t in iter {
1874            self.insert(&t);
1875        }
1876    }
1877}
1878
1879impl<'b, T: Into<TripleRef<'b>>> Extend<T> for GraphViewMut<'_> {
1880    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1881        for t in iter {
1882            self.insert(t);
1883        }
1884    }
1885}
1886
1887impl<'a> IntoIterator for &'a GraphViewMut<'a> {
1888    type Item = TripleRef<'a>;
1889    type IntoIter = GraphViewIter<'a>;
1890
1891    fn into_iter(self) -> Self::IntoIter {
1892        self.iter()
1893    }
1894}
1895
1896impl fmt::Display for GraphViewMut<'_> {
1897    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1898        for t in self {
1899            writeln!(f, "{t}")?;
1900        }
1901        Ok(())
1902    }
1903}
1904
1905/// Iterator returned by [`Dataset::iter`].
1906pub struct Iter<'a> {
1907    dataset: &'a Dataset,
1908    inner: std::collections::btree_set::Iter<
1909        'a,
1910        (
1911            InternedNamedOrBlankNode,
1912            InternedNamedNode,
1913            InternedTerm,
1914            InternedGraphName,
1915        ),
1916    >,
1917}
1918
1919impl<'a> Iterator for Iter<'a> {
1920    type Item = QuadRef<'a>;
1921
1922    fn next(&mut self) -> Option<Self::Item> {
1923        self.inner
1924            .next()
1925            .map(|(s, p, o, g)| self.dataset.decode_spog((s, p, o, g)))
1926    }
1927}
1928
1929/// Iterator returned by [`GraphView::iter`].
1930pub struct GraphViewIter<'a> {
1931    dataset: &'a Dataset,
1932    inner: std::collections::btree_set::Range<
1933        'a,
1934        (
1935            InternedGraphName,
1936            InternedNamedOrBlankNode,
1937            InternedNamedNode,
1938            InternedTerm,
1939        ),
1940    >,
1941}
1942
1943impl<'a> Iterator for GraphViewIter<'a> {
1944    type Item = TripleRef<'a>;
1945
1946    fn next(&mut self) -> Option<Self::Item> {
1947        self.inner
1948            .next()
1949            .map(|(_, s, p, o)| self.dataset.decode_spo((s, p, o)))
1950    }
1951}
1952
1953type QuadsPerBlankNode<'a> = HashMap<
1954    InternedBlankNode,
1955    Vec<&'a (
1956        InternedNamedOrBlankNode,
1957        InternedNamedNode,
1958        InternedTerm,
1959        InternedGraphName,
1960    )>,
1961>;
1962
1963/// An algorithm used to canonicalize graph and datasets.
1964///
1965/// See [`Graph::canonicalize`] and [`Dataset::canonicalize`].
1966#[derive(Default, Debug, Clone, Copy, Eq, PartialEq, Hash)]
1967#[non_exhaustive]
1968pub enum CanonicalizationAlgorithm {
1969    /// The algorithm preferred by OxRDF.
1970    ///
1971    /// <div class="warning">The canonicalization algorithm is not stable and canonical blank node ids might change between versions.</div>
1972    #[default]
1973    Unstable,
1974    /// The [RDF Canonicalization algorithm version 1.0](https://www.w3.org/TR/rdf-canon/#dfn-rdfc-1-0) parametrized with its used [`CanonicalizationHashAlgorithm`](hash algorithm).
1975    ///
1976    /// <div class="warning">Note that the algorithm does not support RDF 1.2, this implementation behavior on triple terms is not part of the standard and might change.</div>
1977    #[cfg(feature = "rdfc-10")]
1978    Rdfc10 {
1979        hash_algorithm: CanonicalizationHashAlgorithm,
1980    },
1981}
1982
1983/// The hash function to use to canonicalize graph and datasets.
1984///
1985/// See [`Graph::canonicalize`] and [`Dataset::canonicalize`].
1986#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash)]
1987#[non_exhaustive]
1988pub enum CanonicalizationHashAlgorithm {
1989    #[cfg(feature = "rdfc-10")]
1990    Sha256,
1991    #[cfg(feature = "rdfc-10")]
1992    Sha384,
1993}
1994
1995/// A RDFC [canonicalization state](https://www.w3.org/TR/rdf-canon/#canon-state)
1996struct CanonicalizationState<'a> {
1997    blank_node_to_quads_map: QuadsPerBlankNode<'a>,
1998    hash_to_blank_nodes_map: BTreeMap<String, Vec<InternedBlankNode>>,
1999    canonical_issuer: IdentifierIssuer,
2000}
2001
2002/// A RDFC [identifier issuer](https://www.w3.org/TR/rdf-canon/#dfn-identifier-issuer)
2003#[derive(Clone)]
2004struct IdentifierIssuer {
2005    identifier_prefix: &'static str,
2006    identifier_counter: u32,
2007    issued_identifier_map: HashMap<InternedBlankNode, BlankNode>,
2008    issued_identifier_order: Vec<InternedBlankNode>, /* hack to know the insertion order in the hash map */
2009}
2010
2011impl IdentifierIssuer {
2012    fn new(identifier_prefix: &'static str) -> Self {
2013        Self {
2014            identifier_prefix,
2015            identifier_counter: 0,
2016            issued_identifier_map: HashMap::new(),
2017            issued_identifier_order: Vec::new(),
2018        }
2019    }
2020}
2021
2022fn generate_permutations<T: Copy>(items: impl IntoIterator<Item = T>) -> Vec<Vec<T>> {
2023    let mut current_output = vec![Vec::new()];
2024    for (i, next) in items.into_iter().enumerate() {
2025        let mut new_output = Vec::with_capacity(current_output.len() * (i + 1));
2026        for mut permutation in current_output {
2027            permutation.push(next);
2028            for j in 0..=i {
2029                let mut new_permutation = permutation.clone();
2030                new_permutation.swap(i, j);
2031                new_output.push(new_permutation);
2032            }
2033        }
2034        current_output = new_output;
2035    }
2036    current_output
2037}
2038
2039#[cfg(feature = "rdfc-10")]
2040#[cfg(test)]
2041mod tests {
2042    use super::*;
2043
2044    #[test]
2045    fn test_canon() {
2046        let p = NamedNode::new_unchecked("http://example.com/#p");
2047        let q = NamedNode::new_unchecked("http://example.com/#q");
2048        let r = NamedNode::new_unchecked("http://example.com/#r");
2049
2050        let mut dataset = Dataset::new();
2051        let e0 = BlankNode::new_unchecked("e0");
2052        let e1 = BlankNode::new_unchecked("e1");
2053        let e2 = BlankNode::new_unchecked("e2");
2054        let e3 = BlankNode::new_unchecked("e3");
2055        dataset.insert(QuadRef::new(&p, &q, &e0, GraphNameRef::DefaultGraph));
2056        dataset.insert(QuadRef::new(&p, &q, &e1, GraphNameRef::DefaultGraph));
2057        dataset.insert(QuadRef::new(&e0, &p, &e2, GraphNameRef::DefaultGraph));
2058        dataset.insert(QuadRef::new(&e1, &p, &e3, GraphNameRef::DefaultGraph));
2059        dataset.insert(QuadRef::new(&e2, &r, &e3, GraphNameRef::DefaultGraph));
2060        dataset.canonicalize(CanonicalizationAlgorithm::Rdfc10 {
2061            hash_algorithm: CanonicalizationHashAlgorithm::Sha256,
2062        });
2063
2064        let mut expected = Dataset::new();
2065        let c14n0 = BlankNode::new_unchecked("c14n0");
2066        let c14n1 = BlankNode::new_unchecked("c14n1");
2067        let c14n2 = BlankNode::new_unchecked("c14n2");
2068        let c14n3 = BlankNode::new_unchecked("c14n3");
2069        expected.insert(QuadRef::new(&p, &q, &c14n2, GraphNameRef::DefaultGraph));
2070        expected.insert(QuadRef::new(&p, &q, &c14n3, GraphNameRef::DefaultGraph));
2071        expected.insert(QuadRef::new(&c14n0, &r, &c14n1, GraphNameRef::DefaultGraph));
2072        expected.insert(QuadRef::new(&c14n2, &p, &c14n1, GraphNameRef::DefaultGraph));
2073        expected.insert(QuadRef::new(&c14n3, &p, &c14n0, GraphNameRef::DefaultGraph));
2074        assert_eq!(dataset, expected);
2075    }
2076}
oxrdf/dataset.rs

oxrdf/
dataset.rs
