jsonld_core/flattening/
node_map.rs

1use super::Environment;
2use crate::{ExpandedDocument, Id, Indexed, IndexedNode, IndexedObject, Node, 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
287        if let Some(id) = &node.id {
288            let flat_node = match self.nodes.entry(id.clone()) {
289                indexmap::map::Entry::Occupied(occupied) => {
290                    let entry = occupied.into_mut();
291                    if let Some(index) = index {
292                        entry.set_index(Some(index));
293                    }
294                    entry
295                }
296                indexmap::map::Entry::Vacant(vacant) => vacant.insert(Indexed::new(Node::with_id(id.clone()), index)),
297            };
298
299            if let Some(types) = node.types {
300                flat_node.types_mut_or_default().extend(types);
301            }
302
303            flat_node.set_graph_entry(node.graph);
304            flat_node.set_included(node.included);
305            flat_node.properties_mut().extend_unique(node.properties);
306
307            if let Some(props) = node.reverse_properties {
308                flat_node.reverse_properties_or_default().extend_unique(props);
309            }
310        }
311    }
312
313    /// Returns an iterator over the nodes of the graph, in declaration order.
314    #[must_use]
315    pub fn nodes(&self) -> NodeMapGraphNodes<'_, T, B> {
316        self.nodes.values()
317    }
318
319    /// Consumes the graph, returning an iterator over its nodes in
320    /// declaration order.
321    #[must_use]
322    pub fn into_nodes(self) -> IntoNodeMapGraphNodes<T, B> {
323        self.nodes.into_values()
324    }
325}
326
327/// Iterator over the nodes of a graph, in declaration order.
328pub type NodeMapGraphNodes<'a, T, B> = indexmap::map::Values<'a, Id<T, B>, IndexedNode<T, B>>;
329/// Owning iterator over the nodes of a graph, in declaration order.
330pub type IntoNodeMapGraphNodes<T, B> = indexmap::map::IntoValues<Id<T, B>, IndexedNode<T, B>>;
331
332impl<T, B> IntoIterator for NodeMapGraph<T, B> {
333    type Item = (Id<T, B>, IndexedNode<T, B>);
334    type IntoIter = indexmap::map::IntoIter<Id<T, B>, IndexedNode<T, B>>;
335
336    fn into_iter(self) -> Self::IntoIter {
337        self.nodes.into_iter()
338    }
339}
340
341impl<T, B> NodeMapGraph<T, B> {
342    /// Iterates over the nodes of this graph, keyed by identifier.
343    #[must_use]
344    pub fn iter(&self) -> indexmap::map::Iter<'_, Id<T, B>, IndexedNode<T, B>> {
345        self.nodes.iter()
346    }
347}
348
349impl<'a, T, B> IntoIterator for &'a NodeMapGraph<T, B> {
350    type Item = (&'a Id<T, B>, &'a IndexedNode<T, B>);
351    type IntoIter = indexmap::map::Iter<'a, Id<T, B>, IndexedNode<T, B>>;
352
353    fn into_iter(self) -> Self::IntoIter {
354        self.nodes.iter()
355    }
356}
357
358impl<T: Clone + Eq + Hash, B: Clone + Eq + Hash> ExpandedDocument<T, B> {
359    /// Builds the node map of this document using the given vocabulary and
360    /// blank node generator.
361    ///
362    /// # Errors
363    ///
364    /// Returns an error when the generator runs out of identifiers, or when two nodes disagree on an `@index`.
365    pub fn generate_node_map_with<V: VocabularyMut<Iri = T, BlankId = B>, G: LocalGenerator>(
366        &self,
367        vocabulary: &mut V,
368        generator: G,
369    ) -> Result<NodeMap<T, B>, NodeMapError<T, B>> {
370        let mut node_map: NodeMap<T, B> = NodeMap::new();
371        let mut env: Environment<V, G> = Environment::new(vocabulary, generator);
372        for object in self {
373            extend_node_map(&mut env, &mut node_map, object, None)?;
374        }
375        Ok(node_map)
376    }
377}
378
379/// Result of extending a node map with a document fragment.
380pub type ExtendNodeMapResult<V> = Result<
381    IndexedObject<<V as IriVocabulary>::Iri, <V as BlankIdVocabulary>::BlankId>,
382    NodeMapError<<V as IriVocabulary>::Iri, <V as BlankIdVocabulary>::BlankId>,
383>;
384
385/// Extends the `NodeMap` with the given `element` of an expanded JSON-LD document.
386fn extend_node_map<N: VocabularyMut, G: LocalGenerator>(
387    env: &mut Environment<N, G>,
388    node_map: &mut NodeMap<N::Iri, N::BlankId>,
389    element: &IndexedObject<N::Iri, N::BlankId>,
390    active_graph: Option<&Id<N::Iri, N::BlankId>>,
391) -> ExtendNodeMapResult<N>
392where
393    N::Iri: Clone + Eq + Hash,
394    N::BlankId: Clone + Eq + Hash,
395{
396    match element.inner() {
397        Object::Value(value) => {
398            let flat_value = value.clone();
399            Ok(Indexed::new(Object::Value(flat_value), element.index().map(ToOwned::to_owned)))
400        }
401        Object::List(list) => {
402            let mut flat_list = Vec::new();
403
404            for item in list {
405                flat_list.push(extend_node_map(env, node_map, item, active_graph)?);
406            }
407
408            Ok(Indexed::new(Object::List(object::List::new(flat_list)), element.index().map(ToOwned::to_owned)))
409        }
410        Object::Node(node) => {
411            let flat_node = extend_node_map_from_node(env, node_map, node, element.index(), active_graph)?;
412            Ok(flat_node.map_inner(Object::node))
413        }
414    }
415}
416
417type ExtendNodeMapFromNodeResult<T, B> = Result<Indexed<Node<T, B>>, NodeMapError<T, B>>;
418
419fn extend_node_map_from_node<N: VocabularyMut, G: LocalGenerator>(
420    env: &mut Environment<N, G>,
421    node_map: &mut NodeMap<N::Iri, N::BlankId>,
422    node: &Node<N::Iri, N::BlankId>,
423    index: Option<&str>,
424    active_graph: Option<&Id<N::Iri, N::BlankId>>,
425) -> ExtendNodeMapFromNodeResult<N::Iri, N::BlankId>
426where
427    N::Iri: Clone + Eq + Hash,
428    N::BlankId: Clone + Eq + Hash,
429{
430    let id = env.assign_node_id(node.id.as_ref())?;
431
432    {
433        // SAFETY: `active_graph` is always either `None` (default graph) or a
434        // graph id that was previously declared via `node_map.declare_graph`.
435        let flat_node = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked() }.declare_node(id.clone(), index)?;
436
437        if let Some(entry) = node.types.as_deref() {
438            let types: Result<Vec<_>, _> = entry.iter().map(|ty| env.assign_node_id(Some(ty))).collect();
439            flat_node.types = Some(types?);
440        }
441    }
442
443    if let Some(graph_entry) = node.graph_entry() {
444        node_map.declare_graph(id.clone());
445
446        let mut flat_graph: Vec<_> = Vec::new();
447        for object in graph_entry {
448            let flat_object = extend_node_map(env, node_map, object, Some(&id))?;
449            flat_graph.push(flat_object);
450        }
451
452        // SAFETY: `id` was just declared above; `active_graph` is `None` or
453        // declared earlier.
454        let flat_node = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(&id).unwrap_unchecked() };
455        match flat_node.graph_entry_mut() {
456            Some(graph) => graph.extend(flat_graph),
457            None => flat_node.set_graph_entry(Some(flat_graph)),
458        }
459    }
460
461    if let Some(included_entry) = node.included_entry() {
462        for inode in included_entry {
463            extend_node_map_from_node(env, node_map, inode.inner(), inode.index(), active_graph)?;
464        }
465    }
466
467    for (property, objects) in node.properties() {
468        // "If property is a blank node identifier, replace it with a newly
469        // generated blank node identifier" — properties share the relabeling
470        // map with node identifiers (`flatten#t0038`).
471        let property = env.assign_node_id(Some(property))?;
472
473        let mut flat_objects = Vec::new();
474        for object in objects {
475            let flat_object = extend_node_map(env, node_map, object, active_graph)?;
476            flat_objects.push(flat_object);
477        }
478        // SAFETY: `id` was declared in this graph above.
479        unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(&id).unwrap_unchecked() }
480            .properties_mut()
481            .insert_all_unique(property, flat_objects);
482    }
483
484    if let Some(reverse_properties) = node.reverse_properties_entry() {
485        for (property, nodes) in reverse_properties {
486            for subject in nodes {
487                let flat_subject = extend_node_map_from_node(env, node_map, subject.inner(), subject.index(), active_graph)?;
488
489                // SAFETY: every flat node produced by `extend_node_map_from_node`
490                // has an `id` set.
491                let subject_id = unsafe { flat_subject.id.as_ref().unwrap_unchecked() };
492
493                // SAFETY: subject was just declared in this graph.
494                let flat_subject = unsafe { node_map.graph_mut(active_graph).unwrap_unchecked().get_mut(subject_id).unwrap_unchecked() };
495
496                flat_subject
497                    .properties_mut()
498                    .insert_unique(property.clone(), Indexed::none(Object::node(Node::with_id(id.clone()))));
499            }
500        }
501    }
502
503    Ok(Indexed::new(Node::with_id(id), None))
504}
jsonld_core/flattening/node_map.rs

jsonld_core/flattening/
node_map.rs
