jsonld_core/flattening/
node_map.rs

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

jsonld_core/flattening/
node_map.rs
