ojak_jsonld/
rdf.rs

1//! RDF, and its canonical form: what a Linked Data Signature signs.
2//!
3//! A Linked Data Signature (`RsaSignature2017`, which Mastodon makes and
4//! checks) does not sign the JSON. It signs the RDF dataset the JSON-LD
5//! means, written out in the canonical N-Quads that the URDNA2015 algorithm
6//! gives — so two documents that say the same thing in different words carry
7//! the same signature, and verifying one means turning it into RDF exactly as
8//! its signer did.
9//!
10//! [`canonize`] does that, from expansion in this crate, through the JSON-LD
11//! 1.1 "Deserialize JSON-LD to RDF" algorithm, to the "Universal RDF Dataset
12//! Normalization Algorithm 2015" ([URDNA2015], which RDFC-1.0 standardised
13//! without changing its output).
14//!
15//! Two things make it stricter than a general processor, both deliberate:
16//!
17//!  -  A context the registry does not hold is an error here, not
18//!     ActivityStreams. A signer resolved it to something; without it, the
19//!     dataset cannot be rebuilt, and guessing would only make the signature
20//!     fail later. A caller that fetches contexts asks
21//!     [`unresolved_contexts`] which ones to add first.
22//!  -  The work is bounded. Expansion is held to [`Limits`]; the blank-node
23//!     labelling, whose worst case is factorial in the number of blank nodes
24//!     that look alike, is held to a budget of its own and gives up with
25//!     [`Error::CanonicalizationBudgetExceeded`] rather than run away.
26//!
27//! [URDNA2015]: https://www.w3.org/TR/rdf-canon/
28
29use alloc::{
30    borrow::ToOwned,
31    collections::{BTreeMap, BTreeSet},
32    format,
33    string::{String, ToString},
34    vec::Vec,
35};
36use serde_json::{Map, Value};
37use sha2::{Digest, Sha256};
38
39use crate::{
40    Error, Limits, Registry,
41    context::{ActiveContext, Session, is_absolute_iri},
42    expand,
43};
44
45const RDF_TYPE: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#type";
46const RDF_FIRST: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#first";
47const RDF_REST: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#rest";
48const RDF_NIL: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#nil";
49const RDF_LANG_STRING: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#langString";
50const XSD_STRING: &str = "http://www.w3.org/2001/XMLSchema#string";
51const XSD_BOOLEAN: &str = "http://www.w3.org/2001/XMLSchema#boolean";
52const XSD_INTEGER: &str = "http://www.w3.org/2001/XMLSchema#integer";
53const XSD_DOUBLE: &str = "http://www.w3.org/2001/XMLSchema#double";
54
55/// How many steps the blank-node labelling may take for one dataset.
56///
57/// Each step is one call of "Hash N-Degree Quads" or one permutation it
58/// tries. An ActivityPub document has a handful of blank nodes, nearly all
59/// told apart at the first degree, and takes none.
60const CANONICALIZATION_BUDGET: usize = 4_096;
61
62/// A node or value in an RDF statement.
63#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
64pub enum Term {
65    /// An absolute IRI.
66    Iri(String),
67    /// A blank node, by its label without the leading `_:`.
68    Blank(String),
69    /// A literal: its lexical form, its datatype IRI, and its language tag
70    /// when the datatype is `rdf:langString`.
71    Literal {
72        value: String,
73        datatype: String,
74        language: Option<String>,
75    },
76}
77
78/// One RDF statement, in the default graph or a named one.
79#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
80pub struct Quad {
81    pub subject: Term,
82    pub predicate: String,
83    pub object: Term,
84    /// `None` for the default graph.
85    pub graph: Option<Term>,
86}
87
88/// Expand `document` the way RDF needs it, refusing a context ojak does not
89/// ship.
90///
91/// The result differs from [`crate::expand`] in two places, both where
92/// ojak's reading expansion drops what says nothing to a tree reader but
93/// is a statement in RDF: a node object with no properties is kept (it is a
94/// blank node something points at), and a term whose `@container` is
95/// `@graph` wraps its values in a graph object.
96pub fn expand_for_rdf(
97    registry: &Registry,
98    document: &Value,
99    limits: Limits,
100) -> Result<Value, Error> {
101    let mut session = Session::new(registry, limits);
102    session.rdf = true;
103    let expanded = expand::expand_document(&ActiveContext::default(), document, &mut session)?;
104    if let Some(unresolved) = session.unresolved.into_iter().next() {
105        return Err(Error::UnresolvedContext(unresolved));
106    }
107    Ok(expanded)
108}
109
110/// Every context `document` names, directly or through a context it names,
111/// that `registry` does not hold: what a caller that fetches contexts has to
112/// fetch before [`canonize`] can succeed.
113///
114/// Each one missing is read as ActivityStreams for the rest of the pass, as
115/// [`crate::expand`] reads it, so that one pass finds every one the
116/// document names itself; a context one of those names in turn is found
117/// once that one has been added. Empty when nothing is missing.
118///
119/// # Errors
120///
121/// When the document cannot be expanded for some reason other than a
122/// missing context. An error met after a context was found missing is not
123/// reported, since the missing context may be its cause; the missing ones
124/// are.
125pub fn unresolved_contexts(
126    registry: &Registry,
127    document: &Value,
128    limits: Limits,
129) -> Result<Vec<String>, Error> {
130    let mut session = Session::new(registry, limits);
131    session.rdf = true;
132    let expanded = expand::expand_document(&ActiveContext::default(), document, &mut session);
133    if !session.unresolved.is_empty() {
134        return Ok(session.unresolved);
135    }
136    expanded.map(|_| Vec::new())
137}
138
139/// The canonical N-Quads of `document`: what an `RsaSignature2017` hashes.
140pub fn canonize(registry: &Registry, document: &Value) -> Result<String, Error> {
141    canonize_with(registry, document, Limits::default())
142}
143
144/// [`canonize`], with limits of the caller's choosing.
145pub fn canonize_with(
146    registry: &Registry,
147    document: &Value,
148    limits: Limits,
149) -> Result<String, Error> {
150    let expanded = expand_for_rdf(registry, document, limits)?;
151    let quads = to_rdf(&expanded)?;
152    canonicalize(&quads)
153}
154
155/// The JSON-LD "Deserialize JSON-LD to RDF" algorithm, over a document
156/// [`expand_for_rdf`] expanded.
157///
158/// Statements naming a relative IRI, or a blank node as a predicate, are left
159/// out, as the algorithm leaves them out; so is a literal whose language tag
160/// is not well formed.
161pub fn to_rdf(expanded: &Value) -> Result<Vec<Quad>, Error> {
162    let mut writer = Writer::default();
163    match expanded {
164        Value::Array(items) => {
165            for item in items {
166                writer.node(item, None)?;
167            }
168        }
169        item => {
170            writer.node(item, None)?;
171        }
172    }
173    let mut quads = writer.quads;
174    quads.sort();
175    quads.dedup();
176    Ok(quads)
177}
178
179#[derive(Default)]
180struct Writer {
181    quads: Vec<Quad>,
182    /// Labels the document gave its blank nodes, and what they became.
183    labels: BTreeMap<String, String>,
184    next: usize,
185}
186
187impl Writer {
188    fn fresh(&mut self) -> String {
189        let label = format!("b{}", self.next);
190        self.next += 1;
191        label
192    }
193
194    /// The term for a node's `@id`: an IRI, a blank node relabelled, or
195    /// `None` for a relative IRI, which RDF cannot name.
196    fn id_term(&mut self, id: &str) -> Option<Term> {
197        if let Some(label) = id.strip_prefix("_:") {
198            if let Some(mapped) = self.labels.get(label) {
199                return Some(Term::Blank(mapped.clone()));
200            }
201            let mapped = self.fresh();
202            self.labels.insert(label.to_owned(), mapped.clone());
203            return Some(Term::Blank(mapped));
204        }
205        well_formed_iri(id).then(|| Term::Iri(id.to_owned()))
206    }
207
208    fn emit(&mut self, subject: &Term, predicate: &str, object: Term, graph: &Option<Term>) {
209        self.quads.push(Quad {
210            subject: subject.clone(),
211            predicate: predicate.to_owned(),
212            object,
213            graph: graph.clone(),
214        });
215    }
216
217    /// Write a node object's statements into `graph`, returning the term
218    /// that names it (`None` when its `@id` is a relative IRI).
219    fn node(&mut self, node: &Value, graph: Option<Term>) -> Result<Option<Term>, Error> {
220        let Value::Object(map) = node else {
221            return Ok(None);
222        };
223        if map.contains_key("@value") || map.contains_key("@list") {
224            // A value at the top level is a statement about nothing.
225            return Ok(None);
226        }
227        if let Some(contents) = map.get("@graph") {
228            return self.graph_object(map, contents);
229        }
230        let subject = match map.get("@id").and_then(Value::as_str) {
231            Some(id) => self.id_term(id),
232            None => Some(Term::Blank(self.fresh())),
233        };
234
235        let mut keys: Vec<&String> = map.keys().collect();
236        keys.sort();
237        for key in keys {
238            let values = match &map[key] {
239                Value::Array(items) => items.as_slice(),
240                single => core::slice::from_ref(single),
241            };
242            match key.as_str() {
243                "@id" => {}
244                "@type" => {
245                    for kind in values {
246                        let Some(kind) = kind.as_str() else { continue };
247                        let object = self.id_term(kind);
248                        if let (Some(subject), Some(object)) = (&subject, object) {
249                            self.emit(subject, RDF_TYPE, object, &graph);
250                        }
251                    }
252                }
253                key if key.starts_with('@') => {}
254                property => {
255                    let usable = well_formed_iri(property);
256                    for value in values {
257                        let object = self.object(value, &graph)?;
258                        if let (true, Some(subject), Some(object)) = (usable, &subject, object) {
259                            self.emit(subject, property, object, &graph);
260                        }
261                    }
262                }
263            }
264        }
265        Ok(subject)
266    }
267
268    /// A graph object: its nodes go into a graph named by its `@id`, or by a
269    /// fresh blank node, and that name is what refers to it.
270    fn graph_object(
271        &mut self,
272        map: &Map<String, Value>,
273        contents: &Value,
274    ) -> Result<Option<Term>, Error> {
275        let name = match map.get("@id").and_then(Value::as_str) {
276            Some(id) => self.id_term(id),
277            None => Some(Term::Blank(self.fresh())),
278        };
279        let items = match contents {
280            Value::Array(items) => items.as_slice(),
281            single => core::slice::from_ref(single),
282        };
283        for item in items {
284            // Statements whose graph cannot be named are not statements.
285            if name.is_some() {
286                self.node(item, name.clone())?;
287            }
288        }
289        Ok(name)
290    }
291
292    /// The term for one value of a property, writing whatever it needs: a
293    /// node's own statements, or a list's cells.
294    fn object(&mut self, value: &Value, graph: &Option<Term>) -> Result<Option<Term>, Error> {
295        let Value::Object(map) = value else {
296            return Ok(None);
297        };
298        if map.contains_key("@value") {
299            return literal(map);
300        }
301        if let Some(items) = map.get("@list") {
302            let items = match items {
303                Value::Array(items) => items.as_slice(),
304                single => core::slice::from_ref(single),
305            };
306            return self.list(items, graph);
307        }
308        self.node(value, graph.clone())
309    }
310
311    /// The JSON-LD "List to RDF Conversion" algorithm.
312    fn list(&mut self, items: &[Value], graph: &Option<Term>) -> Result<Option<Term>, Error> {
313        if items.is_empty() {
314            return Ok(Some(Term::Iri(RDF_NIL.to_owned())));
315        }
316        let cells: Vec<Term> = items.iter().map(|_| Term::Blank(self.fresh())).collect();
317        for (index, item) in items.iter().enumerate() {
318            let cell = &cells[index];
319            if let Some(object) = self.object(item, graph)? {
320                self.emit(cell, RDF_FIRST, object, graph);
321            }
322            let rest = cells
323                .get(index + 1)
324                .cloned()
325                .unwrap_or_else(|| Term::Iri(RDF_NIL.to_owned()));
326            self.emit(cell, RDF_REST, rest, graph);
327        }
328        Ok(cells.into_iter().next())
329    }
330}
331
332/// The JSON-LD "Object to RDF Conversion" algorithm, for a value object.
333fn literal(map: &Map<String, Value>) -> Result<Option<Term>, Error> {
334    let value = &map["@value"];
335    let datatype = map.get("@type").and_then(Value::as_str);
336    if datatype == Some("@json") {
337        return Err(Error::Unsupported("@json literal".to_owned()));
338    }
339    if let Some(datatype) = datatype
340        && !well_formed_iri(datatype)
341    {
342        return Ok(None);
343    }
344    let language = map.get("@language").and_then(Value::as_str);
345    let (lexical, datatype) = match value {
346        Value::Bool(flag) => (
347            if *flag { "true" } else { "false" }.to_owned(),
348            datatype.unwrap_or(XSD_BOOLEAN).to_owned(),
349        ),
350        Value::Number(number) => {
351            let double = number.as_f64().unwrap_or(0.0);
352            // Every double from 2^53 up is integral; below, one is when it
353            // survives a round trip through an integer.
354            #[allow(clippy::cast_possible_truncation, clippy::cast_precision_loss)]
355            let integral = number.is_i64()
356                || number.is_u64()
357                || double.abs() >= 9_007_199_254_740_992.0
358                || (double as i64) as f64 == double;
359            if !integral || double.abs() >= 1e21 || datatype == Some(XSD_DOUBLE) {
360                (
361                    canonical_double(double),
362                    datatype.unwrap_or(XSD_DOUBLE).to_owned(),
363                )
364            } else {
365                let lexical = if let Some(integer) = number.as_i64() {
366                    integer.to_string()
367                } else if let Some(integer) = number.as_u64() {
368                    integer.to_string()
369                } else {
370                    // An integral double below 10^21: written without a
371                    // fraction, as the integer it is.
372                    format!("{double:.0}")
373                };
374                (lexical, datatype.unwrap_or(XSD_INTEGER).to_owned())
375            }
376        }
377        Value::String(text) => match (language, datatype) {
378            (Some(language), _) => {
379                if !well_formed_language(language) {
380                    return Ok(None);
381                }
382                return Ok(Some(Term::Literal {
383                    value: text.clone(),
384                    datatype: RDF_LANG_STRING.to_owned(),
385                    language: Some(language.to_owned()),
386                }));
387            }
388            (None, Some(datatype)) => (text.clone(), datatype.to_owned()),
389            (None, None) => (text.clone(), XSD_STRING.to_owned()),
390        },
391        _ => {
392            return Err(Error::Unsupported(
393                "a value object whose @value is not a scalar".to_owned(),
394            ));
395        }
396    };
397    Ok(Some(Term::Literal {
398        value: lexical,
399        datatype,
400        language: None,
401    }))
402}
403
404/// XSD's canonical double, as JSON-LD writes it: `%1.15E` with the fraction's
405/// trailing zeros removed, one digit kept (`5.0E-1`, `1.0E21`).
406fn canonical_double(value: f64) -> String {
407    if value == 0.0 {
408        // Negative zero too: RDF.rb writes both as the one zero.
409        return "0.0E0".to_owned();
410    }
411    let formatted = format!("{value:.15E}");
412    let (mantissa, exponent) = formatted.split_once('E').unwrap_or((&formatted, "0"));
413    let (whole, fraction) = mantissa.split_once('.').unwrap_or((mantissa, ""));
414    let fraction = fraction.trim_end_matches('0');
415    let fraction = if fraction.is_empty() { "0" } else { fraction };
416    format!("{whole}.{fraction}E{exponent}")
417}
418
419/// An absolute IRI, as RFC 3987 has it: a statement naming anything else —
420/// a relative reference, or `a#b#c` — is not one.
421fn well_formed_iri(value: &str) -> bool {
422    is_absolute_iri(value) && iri_string::types::IriStr::new(value).is_ok()
423}
424
425/// BCP 47 as N-Quads reads it: `[a-zA-Z]+ ('-' [a-zA-Z0-9]+)*`.
426fn well_formed_language(tag: &str) -> bool {
427    let mut parts = tag.split('-');
428    let first = parts.next().unwrap_or("");
429    !first.is_empty()
430        && first.chars().all(|c| c.is_ascii_alphabetic())
431        && parts.all(|part| !part.is_empty() && part.chars().all(|c| c.is_ascii_alphanumeric()))
432}
433
434/// URDNA2015: the dataset's canonical N-Quads, one statement a line, sorted.
435pub fn canonicalize(quads: &[Quad]) -> Result<String, Error> {
436    let mut state = Canonicalizer::new(quads);
437    state.label()?;
438    let mut lines: Vec<String> = quads
439        .iter()
440        .map(|quad| state.relabelled(quad))
441        .map(|quad| nquad(&quad))
442        .collect();
443    lines.sort();
444    lines.dedup();
445    Ok(lines.concat())
446}
447
448/// An identifier issuer: hands out `prefix0`, `prefix1`, … in order, the same
449/// one each time it is asked about the same blank node.
450#[derive(Clone, Debug)]
451struct Issuer {
452    prefix: &'static str,
453    issued: BTreeMap<String, String>,
454    order: Vec<String>,
455}
456
457impl Issuer {
458    fn new(prefix: &'static str) -> Self {
459        Self {
460            prefix,
461            issued: BTreeMap::new(),
462            order: Vec::new(),
463        }
464    }
465
466    fn issue(&mut self, existing: &str) -> String {
467        if let Some(issued) = self.issued.get(existing) {
468            return issued.clone();
469        }
470        let issued = format!("{}{}", self.prefix, self.order.len());
471        self.issued.insert(existing.to_owned(), issued.clone());
472        self.order.push(existing.to_owned());
473        issued
474    }
475
476    fn get(&self, existing: &str) -> Option<&String> {
477        self.issued.get(existing)
478    }
479}
480
481struct Canonicalizer<'a> {
482    quads: &'a [Quad],
483    /// Each blank node, and the statements mentioning it.
484    mentions: BTreeMap<String, Vec<usize>>,
485    canonical: Issuer,
486    first_degree: BTreeMap<String, String>,
487    budget: usize,
488}
489
490fn blank(term: &Term) -> Option<&str> {
491    match term {
492        Term::Blank(label) => Some(label),
493        _ => None,
494    }
495}
496
497impl<'a> Canonicalizer<'a> {
498    fn new(quads: &'a [Quad]) -> Self {
499        let mut mentions: BTreeMap<String, Vec<usize>> = BTreeMap::new();
500        for (index, quad) in quads.iter().enumerate() {
501            let mut seen = BTreeSet::new();
502            for term in [Some(&quad.subject), Some(&quad.object), quad.graph.as_ref()]
503                .into_iter()
504                .flatten()
505            {
506                if let Some(label) = blank(term)
507                    && seen.insert(label)
508                {
509                    mentions.entry(label.to_owned()).or_default().push(index);
510                }
511            }
512        }
513        Self {
514            quads,
515            mentions,
516            canonical: Issuer::new("c14n"),
517            first_degree: BTreeMap::new(),
518            budget: CANONICALIZATION_BUDGET,
519        }
520    }
521
522    fn spend(&mut self) -> Result<(), Error> {
523        self.budget = self
524            .budget
525            .checked_sub(1)
526            .ok_or(Error::CanonicalizationBudgetExceeded)?;
527        Ok(())
528    }
529
530    /// Steps 3 to 6 of the algorithm: every blank node gets its canonical
531    /// label.
532    fn label(&mut self) -> Result<(), Error> {
533        let nodes: Vec<String> = self.mentions.keys().cloned().collect();
534        let mut by_hash: BTreeMap<String, Vec<String>> = BTreeMap::new();
535        for node in &nodes {
536            let hash = self.hash_first_degree(node);
537            by_hash.entry(hash).or_default().push(node.clone());
538        }
539        // A hash only one node has names that node.
540        let mut shared = Vec::new();
541        for (_, group) in by_hash {
542            if group.len() == 1 {
543                self.canonical.issue(&group[0]);
544            } else {
545                shared.push(group);
546            }
547        }
548        for group in shared {
549            let mut results = Vec::new();
550            for node in group {
551                if self.canonical.get(&node).is_some() {
552                    continue;
553                }
554                let mut issuer = Issuer::new("b");
555                issuer.issue(&node);
556                results.push(self.hash_n_degree(&node, issuer)?);
557            }
558            results.sort_by(|a, b| a.0.cmp(&b.0));
559            for (_, issuer) in results {
560                for existing in &issuer.order {
561                    self.canonical.issue(existing);
562                }
563            }
564        }
565        Ok(())
566    }
567
568    /// "Hash First Degree Quads".
569    fn hash_first_degree(&mut self, node: &str) -> String {
570        if let Some(hash) = self.first_degree.get(node) {
571            return hash.clone();
572        }
573        let mut lines: Vec<String> = self.mentions[node]
574            .iter()
575            .map(|&index| {
576                let quad = &self.quads[index];
577                let mark = |term: &Term| match term {
578                    Term::Blank(label) if label == node => Term::Blank("a".to_owned()),
579                    Term::Blank(_) => Term::Blank("z".to_owned()),
580                    other => other.clone(),
581                };
582                nquad(&Quad {
583                    subject: mark(&quad.subject),
584                    predicate: quad.predicate.clone(),
585                    object: mark(&quad.object),
586                    graph: quad.graph.as_ref().map(mark),
587                })
588            })
589            .collect();
590        lines.sort();
591        let hash = sha256_hex(lines.concat().as_bytes());
592        self.first_degree.insert(node.to_owned(), hash.clone());
593        hash
594    }
595
596    /// "Hash Related Blank Node".
597    fn hash_related(
598        &mut self,
599        related: &str,
600        quad: &Quad,
601        issuer: &Issuer,
602        position: &str,
603    ) -> String {
604        let identifier = match (self.canonical.get(related), issuer.get(related)) {
605            (Some(id), _) | (None, Some(id)) => format!("_:{id}"),
606            (None, None) => self.hash_first_degree(related),
607        };
608        let mut input = String::from(position);
609        if position != "g" {
610            input.push('<');
611            input.push_str(&quad.predicate);
612            input.push('>');
613        }
614        input.push_str(&identifier);
615        sha256_hex(input.as_bytes())
616    }
617
618    /// "Hash N-Degree Quads".
619    fn hash_n_degree(&mut self, node: &str, mut issuer: Issuer) -> Result<(String, Issuer), Error> {
620        self.spend()?;
621        let mut related_by_hash: BTreeMap<String, Vec<String>> = BTreeMap::new();
622        let mentions = self.mentions[node].clone();
623        for index in mentions {
624            let quad = &self.quads[index];
625            for (term, position) in [
626                (Some(&quad.subject), "s"),
627                (Some(&quad.object), "o"),
628                (quad.graph.as_ref(), "g"),
629            ] {
630                let Some(related) = term.and_then(blank) else {
631                    continue;
632                };
633                if related == node {
634                    continue;
635                }
636                let hash = self.hash_related(related, quad, &issuer, position);
637                related_by_hash
638                    .entry(hash)
639                    .or_default()
640                    .push(related.to_owned());
641            }
642        }
643
644        let mut data = String::new();
645        for (hash, related) in related_by_hash {
646            data.push_str(&hash);
647            let mut chosen_path = String::new();
648            let mut chosen_issuer: Option<Issuer> = None;
649            for permutation in permutations(&related) {
650                self.spend()?;
651                let mut issuer_copy = issuer.clone();
652                let mut path = String::new();
653                let mut recursion = Vec::new();
654                let mut skip = false;
655                for node in &permutation {
656                    if let Some(id) = self.canonical.get(node) {
657                        path.push_str("_:");
658                        path.push_str(id);
659                    } else {
660                        if issuer_copy.get(node).is_none() {
661                            recursion.push(node.clone());
662                        }
663                        path.push_str("_:");
664                        path.push_str(&issuer_copy.issue(node));
665                    }
666                    if !chosen_path.is_empty()
667                        && path.len() >= chosen_path.len()
668                        && path > chosen_path
669                    {
670                        skip = true;
671                        break;
672                    }
673                }
674                if skip {
675                    continue;
676                }
677                for node in recursion {
678                    let (result_hash, result_issuer) =
679                        self.hash_n_degree(&node, issuer_copy.clone())?;
680                    path.push_str("_:");
681                    path.push_str(&issuer_copy.issue(&node));
682                    path.push('<');
683                    path.push_str(&result_hash);
684                    path.push('>');
685                    issuer_copy = result_issuer;
686                    if !chosen_path.is_empty()
687                        && path.len() >= chosen_path.len()
688                        && path > chosen_path
689                    {
690                        skip = true;
691                        break;
692                    }
693                }
694                if skip {
695                    continue;
696                }
697                if chosen_path.is_empty() || path < chosen_path {
698                    chosen_path = path;
699                    chosen_issuer = Some(issuer_copy);
700                }
701            }
702            data.push_str(&chosen_path);
703            if let Some(chosen) = chosen_issuer {
704                issuer = chosen;
705            }
706        }
707        Ok((sha256_hex(data.as_bytes()), issuer))
708    }
709
710    fn relabelled(&self, quad: &Quad) -> Quad {
711        let relabel = |term: &Term| match term {
712            Term::Blank(label) => Term::Blank(
713                self.canonical
714                    .get(label)
715                    .cloned()
716                    .unwrap_or_else(|| label.clone()),
717            ),
718            other => other.clone(),
719        };
720        Quad {
721            subject: relabel(&quad.subject),
722            predicate: quad.predicate.clone(),
723            object: relabel(&quad.object),
724            graph: quad.graph.as_ref().map(relabel),
725        }
726    }
727}
728
729/// Every ordering of `items`, one at a time: all of them at once would be
730/// factorial in memory before the budget had a say.
731struct Permutations<'a> {
732    items: &'a [String],
733    order: Option<Vec<usize>>,
734}
735
736fn permutations(items: &[String]) -> Permutations<'_> {
737    Permutations {
738        items,
739        order: Some((0..items.len()).collect()),
740    }
741}
742
743impl Iterator for Permutations<'_> {
744    type Item = Vec<String>;
745
746    fn next(&mut self) -> Option<Vec<String>> {
747        let order = self.order.as_mut()?;
748        let current = order.iter().map(|&i| self.items[i].clone()).collect();
749        // The next ordering in lexicographic order of the indices, or none.
750        match (1..order.len()).rev().find(|&i| order[i - 1] < order[i]) {
751            Some(pivot) => {
752                let swap = (pivot..order.len())
753                    .rev()
754                    .find(|&j| order[j] > order[pivot - 1])
755                    .unwrap_or(pivot);
756                order.swap(pivot - 1, swap);
757                order[pivot..].reverse();
758            }
759            None => self.order = None,
760        }
761        Some(current)
762    }
763}
764
765fn sha256_hex(bytes: &[u8]) -> String {
766    let digest = Sha256::digest(bytes);
767    let mut hex = String::with_capacity(64);
768    for byte in digest {
769        hex.push_str(&format!("{byte:02x}"));
770    }
771    hex
772}
773
774/// One statement in canonical N-Quads, with its line ending.
775fn nquad(quad: &Quad) -> String {
776    let mut line = String::new();
777    write_term(&mut line, &quad.subject);
778    line.push_str(" <");
779    line.push_str(&quad.predicate);
780    line.push_str("> ");
781    write_term(&mut line, &quad.object);
782    if let Some(graph) = &quad.graph {
783        line.push(' ');
784        write_term(&mut line, graph);
785    }
786    line.push_str(" .\n");
787    line
788}
789
790fn write_term(out: &mut String, term: &Term) {
791    match term {
792        Term::Iri(iri) => {
793            out.push('<');
794            out.push_str(iri);
795            out.push('>');
796        }
797        Term::Blank(label) => {
798            out.push_str("_:");
799            out.push_str(label);
800        }
801        Term::Literal {
802            value,
803            datatype,
804            language,
805        } => {
806            out.push('"');
807            for c in value.chars() {
808                match c {
809                    '\\' => out.push_str("\\\\"),
810                    '"' => out.push_str("\\\""),
811                    '\n' => out.push_str("\\n"),
812                    '\r' => out.push_str("\\r"),
813                    '\t' => out.push_str("\\t"),
814                    '\u{8}' => out.push_str("\\b"),
815                    '\u{c}' => out.push_str("\\f"),
816                    c if (c as u32) < 0x20 || c == '\u{7f}' => {
817                        out.push_str(&format!("\\u{:04X}", c as u32));
818                    }
819                    c => out.push(c),
820                }
821            }
822            out.push('"');
823            if let Some(language) = language {
824                out.push('@');
825                out.push_str(language);
826            } else if datatype != XSD_STRING {
827                out.push_str("^^<");
828                out.push_str(datatype);
829                out.push('>');
830            }
831        }
832    }
833}
834
835#[cfg(test)]
836mod tests {
837    use super::*;
838
839    #[test]
840    fn doubles_are_written_as_xsd_writes_them() {
841        assert_eq!(canonical_double(0.5), "5.0E-1");
842        assert_eq!(canonical_double(-0.5), "-5.0E-1");
843        assert_eq!(canonical_double(0.0), "0.0E0");
844        assert_eq!(canonical_double(-0.0), "0.0E0");
845        assert_eq!(canonical_double(1e22), "1.0E22");
846        assert_eq!(canonical_double(0.300_000_000_000_000_04), "3.0E-1");
847        assert_eq!(canonical_double(1.25), "1.25E0");
848    }
849
850    #[test]
851    fn every_ordering_is_tried_once() {
852        let items: Vec<String> = ["a", "b", "c"].iter().map(|s| (*s).to_owned()).collect();
853        let all: Vec<String> = permutations(&items).map(|p| p.concat()).collect();
854        assert_eq!(all, ["abc", "acb", "bac", "bca", "cab", "cba"]);
855        assert_eq!(permutations(&[]).count(), 1);
856    }
857
858    #[test]
859    fn language_tags_are_checked() {
860        assert!(well_formed_language("en"));
861        assert!(well_formed_language("zh-hant-tw"));
862        assert!(!well_formed_language("en_US"));
863        assert!(!well_formed_language(""));
864        assert!(!well_formed_language("en-"));
865    }
866}
ojak_jsonld/rdf.rs

ojak_jsonld/
rdf.rs
