jsonld_core/flattening/
node_map.rs

1use super::Environment;
2use crate::{ExpandedDocument, Id, Indexed, IndexedNode, IndexedObject, Node, NodeParts, Object, hash::IndexMap, object};
3use derive_where::derive_where;
4use rdfx::{
5    LocalGenerator,
6    vocabulary::{BlankIdVocabulary, IriVocabulary, VocabularyMut},
7};
8use std::hash::Hash;
9
10/// Conflicting indexes error.
11///
12/// Raised when a single node is declared with two different indexes.
13#[derive(Clone, Debug, thiserror::Error)]
14#[error("Index `{defined_index}` conflicts with index `{conflicting_index}`")]
15pub struct ConflictingIndexes<T, B> {
16    /// Node carrying the conflicting indexes.
17    pub node_id: Id<T, B>,
18    /// Index already recorded for the node.
19    pub defined_index: String,
20    /// Index that contradicts the recorded one.
21    pub conflicting_index: String,
22}
23
24/// Error returned by node-map construction.
25#[derive(Debug, thiserror::Error)]
26pub enum NodeMapError<T, B> {
27    #[error(transparent)]
28    /// A node was given two different `@index` values.
29    Conflicting(#[from] ConflictingIndexes<T, B>),
30
31    #[error(transparent)]
32    /// A blank node identifier could not be generated.
33    GeneratedId(#[from] crate::id::GeneratedIdError),
34}
35
36/// Default graph of a node map, paired with its named graphs.
37///
38/// Named graphs are yielded in the order they were first declared, which is
39/// document traversal order.
40pub type Parts<T, B> = (NodeMapGraph<T, B>, IndexMap<Id<T, B>, NodeMapGraph<T, B>>);
41
42/// Node identifier to node definition map.
43///
44/// Graphs are stored in declaration order so that flattening is deterministic:
45/// [§4.9 of the JSON-LD API][spec] assigns blank node identifiers in document
46/// traversal order.
47///
48/// [spec]: https://www.w3.org/TR/json-ld11-api/#node-map-generation
49#[derive_where(Default)]
50pub struct NodeMap<T, B> {
51    graphs: IndexMap<Id<T, B>, NodeMapGraph<T, B>>,
52    default_graph: NodeMapGraph<T, B>,
53}
54
55impl<T, B> NodeMap<T, B> {
56    /// Creates a new `NodeMap`.
57    #[must_use]
58    pub fn new() -> Self {
59        Self {
60            graphs: IndexMap::default(),
61            default_graph: NodeMapGraph::new(),
62        }
63    }
64
65    /// Consumes the node map, returning its default graph and named graphs.
66    #[must_use]
67    pub fn into_parts(self) -> Parts<T, B> {
68        (self.default_graph, self.graphs)
69    }
70
71    /// Returns an iterator over the graphs of the node map: the default
72    /// graph first, then the named graphs in declaration order.
73    #[must_use]
74    pub fn iter(&self) -> Iter<'_, T, B> {
75        Iter {
76            default_graph: Some(&self.default_graph),
77            graphs: self.graphs.iter(),
78        }
79    }
80
81    /// Returns an iterator over the named graphs only, in declaration order.
82    #[must_use]
83    pub fn iter_named(&self) -> indexmap::map::Iter<'_, Id<T, B>, NodeMapGraph<T, B>> {
84        self.graphs.iter()
85    }
86}
87
88impl<T: Eq + Hash, B: Eq + Hash> NodeMap<T, B> {
89    /// Returns the graph of the given name, or the default graph for `None`,
90    /// if it is declared.
91    #[must_use]
92    pub fn graph(&self, id: Option<&Id<T, B>>) -> Option<&NodeMapGraph<T, B>> {
93        match id {
94            Some(id) => self.graphs.get(id),
95            None => Some(&self.default_graph),
96        }
97    }
98
99    /// Mutably borrows the graph of the given name, if it is declared.
100    pub fn graph_mut(&mut self, id: Option<&Id<T, B>>) -> Option<&mut NodeMapGraph<T, B>> {
101        match id {
102            Some(id) => self.graphs.get_mut(id),
103            None => Some(&mut self.default_graph),
104        }
105    }
106
107    /// Declares a named graph, leaving it untouched if it already exists.
108    pub fn declare_graph(&mut self, id: Id<T, B>) {
109        if let indexmap::map::Entry::Vacant(entry) = self.graphs.entry(id) {
110            entry.insert(NodeMapGraph::new());
111        }
112    }
113
114    /// Merge all the graphs into a single `NodeMapGraph`.
115    ///
116    /// Graphs are merged into the default graph in declaration order.
117    #[must_use]
118    pub fn merge(self) -> NodeMapGraph<T, B>
119    where
120        T: Clone,
121        B: Clone,
122    {
123        let mut result = self.default_graph;
124
125        for (_, graph) in self.graphs {
126            result.merge_with(graph);
127        }
128
129        result
130    }
131}
132
133/// Iterator over the graphs of a node map.
134///
135/// The default graph comes first, then the named graphs in declaration order.
136pub struct Iter<'a, T, B> {
137    default_graph: Option<&'a NodeMapGraph<T, B>>,
138    graphs: indexmap::map::Iter<'a, Id<T, B>, NodeMapGraph<T, B>>,
139}
140
141impl<'a, T, B> Iterator for Iter<'a, T, B> {
142    type Item = (Option<&'a Id<T, B>>, &'a NodeMapGraph<T, B>);
143
144    fn next(&mut self) -> Option<Self::Item> {
145        match self.default_graph.take() {
146            Some(default_graph) => Some((None, default_graph)),
147            None => self.graphs.next().map(|(id, graph)| (Some(id), graph)),
148        }
149    }
150}
151
152impl<'a, T, B> IntoIterator for &'a NodeMap<T, B> {
153    type Item = (Option<&'a Id<T, B>>, &'a NodeMapGraph<T, B>);
154    type IntoIter = Iter<'a, T, B>;
155
156    fn into_iter(self) -> Self::IntoIter {
157        self.iter()
158    }
159}
160
161/// Owning iterator over the graphs of a node map.
162///
163/// The default graph comes first, then the named graphs in declaration order.
164pub struct IntoIter<T, B> {
165    default_graph: Option<NodeMapGraph<T, B>>,
166    graphs: indexmap::map::IntoIter<Id<T, B>, NodeMapGraph<T, B>>,
167}
168
169impl<T, B> Iterator for IntoIter<T, B> {
170    type Item = (Option<Id<T, B>>, NodeMapGraph<T, B>);
171
172    fn next(&mut self) -> Option<Self::Item> {
173        match self.default_graph.take() {
174            Some(default_graph) => Some((None, default_graph)),
175            None => self.graphs.next().map(|(id, graph)| (Some(id), graph)),
176        }
177    }
178}
179
180impl<T, B> IntoIterator for NodeMap<T, B> {
181    type Item = (Option<Id<T, B>>, NodeMapGraph<T, B>);
182    type IntoIter = IntoIter<T, B>;
183
184    fn into_iter(self) -> Self::IntoIter {
185        IntoIter {
186            default_graph: Some(self.default_graph),
187            graphs: self.graphs.into_iter(),
188        }
189    }
190}
191
192#[derive_where(Default)]
193/// Nodes of a single graph within a node map.
194///
195/// Nodes are stored in declaration order; see [`NodeMap`].
196pub struct NodeMapGraph<T, B> {
197    nodes: IndexMap<Id<T, B>, IndexedNode<T, B>>,
198}
199
200impl<T, B> NodeMapGraph<T, B> {
201    /// Creates a new `NodeMapGraph`.
202    #[must_use]
203    pub fn new() -> Self {
204        Self { nodes: IndexMap::default() }
205    }
206}
207
208/// Result of declaring a node in a graph.
209pub type DeclareNodeResult<'a, T, B> = Result<&'a mut Indexed<Node<T, B>>, ConflictingIndexes<T, B>>;
210
211impl<T: Eq + Hash, B: Eq + Hash> NodeMapGraph<T, B> {
212    /// Checks whether the graph declares a node with the given identifier.
213    pub fn contains(&self, id: &Id<T, B>) -> bool {
214        self.nodes.contains_key(id)
215    }
216
217    /// Returns the value bound to the given key, if any.
218    pub fn get(&self, id: &Id<T, B>) -> Option<&IndexedNode<T, B>> {
219        self.nodes.get(id)
220    }
221
222    /// Returns a mutable reference to the value bound to the given key, if any.
223    pub fn get_mut(&mut self, id: &Id<T, B>) -> Option<&mut IndexedNode<T, B>> {
224        self.nodes.get_mut(id)
225    }
226
227    /// Declares a node in this graph, failing if `index` contradicts the index
228    /// already recorded for it.
229    ///
230    /// # Errors
231    ///
232    /// Returns an error when the node is already declared with a conflicting index, or when the generator runs out of identifiers.
233    pub fn declare_node(&mut self, id: Id<T, B>, index: Option<&str>) -> DeclareNodeResult<'_, T, B>
234    where
235        T: Clone,
236        B: Clone,
237    {
238        match self.nodes.entry(id) {
239            indexmap::map::Entry::Occupied(occupied) => match (occupied.get().index(), index) {
240                (Some(entry_index), Some(index)) if entry_index != index => Err(ConflictingIndexes {
241                    node_id: occupied.key().clone(),
242                    defined_index: entry_index.to_string(),
243                    conflicting_index: index.to_string(),
244                }),
245                (None, Some(index)) => {
246                    let entry = occupied.into_mut();
247                    entry.set_index(Some(index.to_owned()));
248                    Ok(entry)
249                }
250                _ => Ok(occupied.into_mut()),
251            },
252            indexmap::map::Entry::Vacant(vacant) => {
253                let node = Indexed::new(Node::with_id(vacant.key().clone()), index.map(ToOwned::to_owned));
254                Ok(vacant.insert(node))
255            }
256        }
257    }
258
259    /// Merges `other` into this graph.
260    ///
261    /// This calls [`merge_node`](Self::merge_node) with every node of `other`.
262    pub fn merge_with(&mut self, other: Self)
263    where
264        T: Clone,
265        B: Clone,
266    {
267        for (_, node) in other {
268            self.merge_node(node);
269        }
270    }
271
272    /// Merges the given `node` into the graph.
273    ///
274    /// The `node` must have an identifier, or this function has no effect.
275    /// If there is already a node with the same identifier:
276    /// - The index of `node`, if any, overrides the previously existing index.
277    /// - The list of `node` types is concatenated after the preexisting types.
278    /// - The graph and imported values are overridden.
279    /// - Properties and reverse properties are merged.
280    pub fn merge_node(&mut self, node: IndexedNode<T, B>)
281    where
282        T: Clone,
283        B: Clone,
284    {
285        let (node, index) = node.into_parts();
286        let NodeParts {
287            id,
288            types,
289            graph,
290            included,
291            properties,
292            reverse_properties,
293        } = node.into_parts();
294
295        if let Some(id) = &id {
296            let flat_node = match self.nodes.entry(id.clone()) {
297                indexmap::map::Entry::Occupied(occupied) => {
298                    let entry = occupied.into_mut();
299                    if let Some(index) = index {
300                        entry.set_index(Some(index));
301                    }
302                    entry
303                }
304                indexmap::map::Entry::Vacant(vacant) => vacant.insert(Indexed::new(Node::with_id(id.clone()), index)),
305            };
306
307            if let Some(types) = types {
308                flat_node.types_mut_or_default().extend(types);
309            }
310
311            flat_node.set_graph_entry(graph);
312            flat_node.set_included(included);
313            flat_node.properties_mut().extend_unique(properties);
314
315            if let Some(props) = reverse_properties {
316                flat_node.reverse_properties_or_default().extend_unique(props);
317            }
318        }
319    }
320
321    /// Returns an iterator over the nodes of the graph, in declaration order.
322    #[must_use]
323    pub fn nodes(&self) -> NodeMapGraphNodes<'_, T, B> {
324        self.nodes.values()
325    }
326
327    /// Consumes the graph, returning an iterator over its nodes in
328    /// declaration order.
329    #[must_use]
330    pub fn into_nodes(self) -> IntoNodeMapGraphNodes<T, B> {
331        self.nodes.into_values()
332    }
333}
334
335/// Iterator over the nodes of a graph, in declaration order.
336pub type NodeMapGraphNodes<'a, T, B> = indexmap::map::Values<'a, Id<T, B>, IndexedNode<T, B>>;
337/// Owning iterator over the nodes of a graph, in declaration order.
338pub type IntoNodeMapGraphNodes<T, B> = indexmap::map::IntoValues<Id<T, B>, IndexedNode<T, B>>;
339
340impl<T, B> IntoIterator for NodeMapGraph<T, B> {
341    type Item = (Id<T, B>, IndexedNode<T, B>);
342    type IntoIter = indexmap::map::IntoIter<Id<T, B>, IndexedNode<T, B>>;
343
344    fn into_iter(self) -> Self::IntoIter {
345        self.nodes.into_iter()
346    }
347}
348
349impl<T, B> NodeMapGraph<T, B> {
350    /// Iterates over the nodes of this graph, keyed by identifier.
351    #[must_use]
352    pub fn iter(&self) -> indexmap::map::Iter<'_, Id<T, B>, IndexedNode<T, B>> {
353        self.nodes.iter()
354    }
355}
356
357impl<'a, T, B> IntoIterator for &'a NodeMapGraph<T, B> {
358    type Item = (&'a Id<T, B>, &'a IndexedNode<T, B>);
359    type IntoIter = indexmap::map::Iter<'a, Id<T, B>, IndexedNode<T, B>>;
360
361    fn into_iter(self) -> Self::IntoIter {
362        self.nodes.iter()
363    }
364}
365
366impl<T: Clone + Eq + Hash, B: Clone + Eq + Hash> ExpandedDocument<T, B> {
367    /// Builds the node map of this document using the given vocabulary and
368    /// blank node generator.
369    ///
370    /// # Errors
371    ///
372    /// Returns an error when the generator runs out of identifiers, or when two nodes disagree on an `@index`.
373    pub fn generate_node_map_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
374        &self,
375        vocabulary: &mut V,
376        generator: G,
377    ) -> Result<NodeMap<T, B>, NodeMapError<T, B>> {
378        let mut node_map: NodeMap<T, B> = NodeMap::new();
379        let mut env: Environment<V, G> = Environment::new(vocabulary, generator);
380        for object in self {
381            extend_node_map(&mut env, &mut node_map, object, None)?;
382        }
383        Ok(node_map)
384    }
385}
386
387/// Result of extending a node map with a document fragment.
388pub type ExtendNodeMapResult<V> = Result<
389    IndexedObject<<V as IriVocabulary>::Iri, <V as BlankIdVocabulary>::BlankId>,
390    NodeMapError<<V as IriVocabulary>::Iri, <V as BlankIdVocabulary>::BlankId>,
391>;
392
393/// Extends the `NodeMap` with the given `element` of an expanded JSON-LD document.
394fn extend_node_map<N: VocabularyMut, G: LocalGenerator>(
395    env: &mut Environment<N, G>,
396    node_map: &mut NodeMap<N::Iri, N::BlankId>,
397    element: &IndexedObject<N::Iri, N::BlankId>,
398    active_graph: Option<&Id<N::Iri, N::BlankId>>,
399) -> ExtendNodeMapResult<N>
400where
401    N::Iri: Clone + Eq + Hash,
402    N::BlankId: Clone + Eq + Hash,
403{
404    match element.inner() {
405        Object::Value(value) => {
406            let flat_value = value.clone();
407            Ok(Indexed::new(Object::Value(flat_value), element.index().map(ToOwned::to_owned)))
408        }
409        Object::List(list) => {
410            let mut flat_list = Vec::new();
411
412            for item in list {
413                flat_list.push(extend_node_map(env, node_map, item, active_graph)?);
414            }
415
416            Ok(Indexed::new(Object::List(object::List::new(flat_list)), element.index().map(ToOwned::to_owned)))
417        }
418        Object::Node(node) => {
419            let flat_node = extend_node_map_from_node(env, node_map, node, element.index(), active_graph)?;
420            Ok(flat_node.map_inner(Object::node))
421        }
422    }
423}
424
425type ExtendNodeMapFromNodeResult<T, B> = Result<Indexed<Node<T, B>>, NodeMapError<T, B>>;
426
427fn extend_node_map_from_node<N: VocabularyMut, G: LocalGenerator>(
428    env: &mut Environment<N, G>,
429    node_map: &mut NodeMap<N::Iri, N::BlankId>,
430    node: &Node<N::Iri, N::BlankId>,
431    index: Option<&str>,
432    active_graph: Option<&Id<N::Iri, N::BlankId>>,
433) -> ExtendNodeMapFromNodeResult<N::Iri, N::BlankId>
434where
435    N::Iri: Clone + Eq + Hash,
436    N::BlankId: Clone + Eq + Hash,
437{
438    let id = env.assign_node_id(node.id.as_ref())?;
439
440    {
441        // SAFETY: `active_graph` is always either `None` (default graph) or a
442        // graph id that was previously declared via `node_map.declare_graph`.
443        let flat_node = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked() }.declare_node(id.clone(), index)?;
444
445        if let Some(entry) = node.types.as_deref() {
446            let types: Result<Vec<_>, _> = entry.iter().map(|ty| env.assign_node_id(Some(ty))).collect();
447            flat_node.types = Some(types?);
448        }
449    }
450
451    if let Some(graph_entry) = node.graph_entry() {
452        node_map.declare_graph(id.clone());
453
454        let mut flat_graph: Vec<_> = Vec::new();
455        for object in graph_entry {
456            let flat_object = extend_node_map(env, node_map, object, Some(&id))?;
457            flat_graph.push(flat_object);
458        }
459
460        // SAFETY: `id` was just declared above; `active_graph` is `None` or
461        // declared earlier.
462        let flat_node = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(&id).unwrap_unchecked() };
463        match flat_node.graph_entry_mut() {
464            Some(graph) => graph.extend(flat_graph),
465            None => flat_node.set_graph_entry(Some(flat_graph)),
466        }
467    }
468
469    if let Some(included_entry) = node.included_entry() {
470        for inode in included_entry {
471            extend_node_map_from_node(env, node_map, inode.inner(), inode.index(), active_graph)?;
472        }
473    }
474
475    for (property, objects) in node.properties() {
476        // "If property is a blank node identifier, replace it with a newly
477        // generated blank node identifier" — properties share the relabeling
478        // map with node identifiers (`flatten#t0038`).
479        let property = env.assign_node_id(Some(property))?;
480
481        let mut flat_objects = Vec::new();
482        for object in objects {
483            let flat_object = extend_node_map(env, node_map, object, active_graph)?;
484            flat_objects.push(flat_object);
485        }
486        // SAFETY: `id` was declared in this graph above.
487        unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(&id).unwrap_unchecked() }
488            .properties_mut()
489            .insert_all_unique(property, flat_objects);
490    }
491
492    if let Some(reverse_properties) = node.reverse_properties_entry() {
493        for (property, nodes) in reverse_properties {
494            for subject in nodes {
495                let flat_subject = extend_node_map_from_node(env, node_map, subject.inner(), subject.index(), active_graph)?;
496
497                // SAFETY: every flat node produced by `extend_node_map_from_node`
498                // has an `id` set.
499                let subject_id = unsafe { flat_subject.id.as_ref().unwrap_unchecked() };
500
501                // SAFETY: subject was just declared in this graph.
502                let flat_subject = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(subject_id).unwrap_unchecked() };
503
504                flat_subject
505                    .properties_mut()
506                    .insert_unique(property.clone(), Indexed::none(Object::node(Node::with_id(id.clone()))));
507            }
508        }
509    }
510
511    Ok(Indexed::new(Node::with_id(id), None))
512}
jsonld_core/flattening/node_map.rs

jsonld_core/flattening/
node_map.rs
