ojak_jsonld/
context.rs

1//! Context processing: turning `@context` values into an active context.
2//!
3//! This follows the JSON-LD 1.1 "Context Processing" and "Create Term
4//! Definition" algorithms closely enough for the contexts the fediverse
5//! actually serves, which is the set in `contexts/`. Those need more than
6//! JSON-LD 1.0: `security/data-integrity/v1` and `cid/v1` define
7//! `DataIntegrityProof` and `Multikey` with *type-scoped* contexts, so a
8//! processor that ignored scoped contexts would fail to expand `proofValue`
9//! and `publicKeyMultibase` — the two fields ojak verifies proofs with.
10//!
11//! What is deliberately left out is recorded in the crate documentation.
12
13use alloc::{
14    borrow::ToOwned,
15    boxed::Box,
16    collections::BTreeMap,
17    string::{String, ToString},
18    sync::Arc,
19    vec::Vec,
20};
21use serde_json::{Map, Value};
22
23use crate::{Error, Limits, Registry};
24
25/// Every JSON-LD keyword, including the ones ojak refuses to process.
26const KEYWORDS: &[&str] = &[
27    "@base",
28    "@container",
29    "@context",
30    "@direction",
31    "@graph",
32    "@id",
33    "@import",
34    "@included",
35    "@index",
36    "@json",
37    "@language",
38    "@list",
39    "@nest",
40    "@none",
41    "@prefix",
42    "@propagate",
43    "@protected",
44    "@reverse",
45    "@set",
46    "@type",
47    "@value",
48    "@version",
49    "@vocab",
50];
51
52/// Whether `value` is a JSON-LD keyword.
53#[must_use]
54pub(crate) fn is_keyword(value: &str) -> bool {
55    KEYWORDS.contains(&value)
56}
57
58/// Whether a simple-string term definition ends in a generic delimiter, which
59/// is what makes it usable as a compact-IRI prefix (`"as"`, `"toot"`, `"gts"`).
60fn ends_with_gen_delim(value: &str) -> bool {
61    matches!(
62        value.chars().next_back(),
63        Some(':' | '/' | '?' | '#' | '[' | ']' | '@')
64    )
65}
66
67/// How a term's values are to be read.
68#[derive(Clone, Debug, Eq, PartialEq)]
69pub(crate) enum TypeMapping {
70    /// `@type: "@id"` — the value is an IRI, not a string.
71    Id,
72    /// `@type: "@vocab"` — the value is an IRI read against `@vocab`.
73    Vocab,
74    /// `@type: "@json"` — the value is a JSON literal, left untouched.
75    Json,
76    /// `@type: "@none"`.
77    None,
78    /// A datatype IRI such as `xsd:dateTime`.
79    Datatype(String),
80}
81
82/// The `@container` flags of a term definition.
83#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
84pub(crate) struct Container {
85    pub list: bool,
86    pub set: bool,
87    pub language: bool,
88    pub index: bool,
89    pub id: bool,
90    pub kind: bool,
91    pub graph: bool,
92}
93
94impl Container {
95    fn add(&mut self, value: &str) {
96        match value {
97            "@list" => self.list = true,
98            "@set" => self.set = true,
99            "@language" => self.language = true,
100            "@index" => self.index = true,
101            "@id" => self.id = true,
102            "@type" => self.kind = true,
103            "@graph" => self.graph = true,
104            _ => {}
105        }
106    }
107}
108
109/// What one term in an active context means.
110#[derive(Clone, Debug, Default, Eq, PartialEq)]
111pub(crate) struct TermDefinition {
112    /// The IRI (or keyword) the term expands to. `None` means the term was
113    /// mapped to `null` and any key using it is dropped.
114    pub iri: Option<String>,
115    pub type_mapping: Option<TypeMapping>,
116    pub container: Container,
117    /// `Some(None)` is `@language: null`, which clears an inherited language.
118    pub language: Option<Option<String>>,
119    pub reverse: bool,
120    pub prefix: bool,
121    pub protected: bool,
122    /// A term-scoped `@context`, applied to this term's values (for a property)
123    /// or to the node carrying it (for a type).
124    pub scoped: Option<Box<Value>>,
125}
126
127/// The context in force at one point in a document.
128///
129/// Expansion hands every node the context of its parent unless the node
130/// brings its own, so this is cloned once per node. The terms are shared
131/// until a context actually changes them, which makes that clone a reference
132/// count rather than a copy of every term the ActivityStreams context defines.
133#[derive(Clone, Debug, Default)]
134pub(crate) struct ActiveContext {
135    terms: Arc<BTreeMap<String, TermDefinition>>,
136    base: Option<String>,
137    vocab: Option<String>,
138    language: Option<String>,
139}
140
141impl ActiveContext {
142    /// Whether nothing has been defined: the context a document starts in.
143    pub(crate) fn is_empty(&self) -> bool {
144        self.terms.is_empty()
145            && self.base.is_none()
146            && self.vocab.is_none()
147            && self.language.is_none()
148    }
149
150    pub(crate) fn term(&self, name: &str) -> Option<&TermDefinition> {
151        self.terms.get(name)
152    }
153
154    pub(crate) fn vocab(&self) -> Option<&str> {
155        self.vocab.as_deref()
156    }
157
158    pub(crate) fn language(&self) -> Option<&str> {
159        self.language.as_deref()
160    }
161
162    pub(crate) fn base(&self) -> Option<&str> {
163        self.base.as_deref()
164    }
165
166    /// Every term, for building the inverse map compaction needs.
167    pub(crate) fn terms(&self) -> impl Iterator<Item = (&String, &TermDefinition)> {
168        self.terms.iter()
169    }
170}
171
172/// Mutable state shared across one document's processing: the budgets, the
173/// registry, and the contexts that could not be resolved.
174pub(crate) struct Session<'a> {
175    pub registry: &'a Registry,
176    pub cache: &'a dyn ContextCache,
177    pub limits: Limits,
178    pub contexts: usize,
179    pub nodes: usize,
180    pub unresolved: Vec<String>,
181    /// Expanding for RDF (`crate::rdf`), which keeps what a tree reader can
182    /// do without but a graph cannot.
183    pub rdf: bool,
184}
185
186impl<'a> Session<'a> {
187    pub(crate) fn new(registry: &'a Registry, limits: Limits) -> Self {
188        Self::with_cache(registry, &NoCache, limits)
189    }
190
191    pub(crate) fn with_cache(
192        registry: &'a Registry,
193        cache: &'a dyn ContextCache,
194        limits: Limits,
195    ) -> Self {
196        Self {
197            registry,
198            cache,
199            limits,
200            contexts: 0,
201            nodes: 0,
202            unresolved: Vec::new(),
203            rdf: false,
204        }
205    }
206
207    pub(crate) fn charge_node(&mut self) -> Result<(), Error> {
208        self.nodes += 1;
209        if self.nodes > self.limits.max_nodes {
210            return Err(Error::NodeBudgetExceeded);
211        }
212        Ok(())
213    }
214
215    fn charge_context(&mut self) -> Result<(), Error> {
216        self.contexts += 1;
217        if self.contexts > self.limits.max_contexts {
218            return Err(Error::ContextBudgetExceeded);
219        }
220        Ok(())
221    }
222
223    fn note_unresolved(&mut self, iri: &str) {
224        if !self.unresolved.iter().any(|seen| seen == iri) {
225            self.unresolved.push(iri.to_owned());
226        }
227    }
228}
229
230/// A `@context` value already processed, kept to be used again.
231///
232/// Holds what processing it produced — the active context — and what it cost
233/// and reported, so that a document using it from a cache is charged and told
234/// exactly what it would have been had it been processed again.
235#[derive(Debug)]
236pub struct ProcessedContext {
237    pub(crate) active: ActiveContext,
238    pub(crate) charged: usize,
239    pub(crate) unresolved: Vec<String>,
240    /// The `@context` value itself, where the caller needs it back.
241    pub(crate) source: Option<Value>,
242}
243
244/// Where processed contexts are kept between documents.
245///
246/// Processing a context costs far more than using one, and nearly every
247/// document a server receives names the same few. This crate is `no_std` and
248/// keeps no state of its own, so the caller supplies the store — behind a
249/// mutex, typically — and decides how much it may hold. A cache holds what one
250/// [`Registry`] resolved, and must be used with that registry only.
251///
252/// Only a document's own top-level `@context` is cached. A context nested in
253/// the document, or scoped to a term, depends on the context around it.
254pub trait ContextCache {
255    /// The context processed under `key`, if kept.
256    fn get(&self, key: &str) -> Option<Arc<ProcessedContext>>;
257    /// Keep a context processed under `key`.
258    fn put(&self, key: String, context: Arc<ProcessedContext>);
259}
260
261/// A [`ContextCache`] that keeps nothing: every context is processed afresh.
262#[derive(Clone, Copy, Debug, Default)]
263pub struct NoCache;
264
265impl ContextCache for NoCache {
266    fn get(&self, _key: &str) -> Option<Arc<ProcessedContext>> {
267        None
268    }
269
270    fn put(&self, _key: String, _context: Arc<ProcessedContext>) {}
271}
272
273/// The key a top-level `@context` is cached under: the value itself, and the
274/// limits it was processed within, which decide whether processing succeeds.
275pub(crate) fn cache_key(local: &Value, limits: &Limits) -> String {
276    let mut key = serde_json::to_string(local).unwrap_or_default();
277    key.push_str(&alloc::format!(
278        "\u{0}{}\u{0}{}",
279        limits.max_contexts,
280        limits.max_terms
281    ));
282    key
283}
284
285/// Process a `@context` value against `active`, returning the new context.
286///
287/// `remote` is the stack of context IRIs currently being resolved, which is how
288/// a context that refers back to itself is caught rather than recursed into.
289/// The ActivityStreams context, which an unknown context is read as.
290const ACTIVITYSTREAMS: &str = "https://www.w3.org/ns/activitystreams";
291
292pub(crate) fn process(
293    active: &ActiveContext,
294    local: &Value,
295    session: &mut Session<'_>,
296    remote: &mut Vec<String>,
297) -> Result<ActiveContext, Error> {
298    // A document's own context, processed first thing from nothing, means
299    // the same wherever it appears; anything later depends on what came
300    // before it, and is processed as it comes.
301    let cacheable = active.is_empty()
302        && remote.is_empty()
303        && session.contexts == 0
304        && session.unresolved.is_empty();
305    if !cacheable {
306        return process_uncached(active, local, session, remote);
307    }
308    let key = cache_key(local, &session.limits);
309    if let Some(cached) = session.cache.get(&key) {
310        session.contexts = cached.charged;
311        if session.contexts > session.limits.max_contexts {
312            return Err(Error::ContextBudgetExceeded);
313        }
314        for iri in &cached.unresolved {
315            session.note_unresolved(iri);
316        }
317        return Ok(cached.active.clone());
318    }
319    let result = process_uncached(active, local, session, remote)?;
320    session.cache.put(
321        key,
322        Arc::new(ProcessedContext {
323            active: result.clone(),
324            charged: session.contexts,
325            unresolved: session.unresolved.clone(),
326            source: None,
327        }),
328    );
329    Ok(result)
330}
331
332fn process_uncached(
333    active: &ActiveContext,
334    local: &Value,
335    session: &mut Session<'_>,
336    remote: &mut Vec<String>,
337) -> Result<ActiveContext, Error> {
338    let mut result = active.clone();
339    let entries: Vec<&Value> = match local {
340        Value::Array(items) => items.iter().collect(),
341        other => Vec::from([other]),
342    };
343
344    for entry in entries {
345        session.charge_context()?;
346        match entry {
347            // A null context wipes the slate, keeping only the document base.
348            Value::Null => {
349                let base = result.base.clone();
350                result = ActiveContext {
351                    base,
352                    ..ActiveContext::default()
353                };
354            }
355            Value::String(iri) => {
356                let resolved = resolve_context_iri(&result, iri);
357                let document = match session.registry.resolve(&resolved) {
358                    Some(document) => document.clone(),
359                    // Tolerant on purpose: a context ojak does not ship does
360                    // not fail the whole document, and the caller is told
361                    // which ones there were. It is read as ActivityStreams:
362                    // every context the fediverse serves extends it (Mbin's
363                    // and Lemmy's own, Pleroma's per-instance LitePub), and
364                    // the sender's own additions, which are all it could add,
365                    // are left unread. Otherwise a document naming only its
366                    // server's context, as Mbin's do, would read as nothing.
367                    None => {
368                        session.note_unresolved(&resolved);
369                        match session.registry.resolve(ACTIVITYSTREAMS) {
370                            Some(document) if resolved != ACTIVITYSTREAMS => document.clone(),
371                            _ => continue,
372                        }
373                    }
374                };
375                if remote.iter().any(|seen| seen == &resolved) {
376                    return Err(Error::CyclicContext(resolved));
377                }
378                remote.push(resolved);
379                let outcome = process(&result, &document, session, remote);
380                remote.pop();
381                result = outcome?;
382            }
383            Value::Object(map) => apply_term_map(&mut result, map, session)?,
384            _ => return Err(Error::InvalidContext),
385        }
386    }
387
388    Ok(result)
389}
390
391/// Resolve a context reference that may be relative to the active base.
392fn resolve_context_iri(active: &ActiveContext, iri: &str) -> String {
393    if is_absolute_iri(iri) {
394        return iri.to_owned();
395    }
396    match active.base() {
397        Some(base) => resolve_against(base, iri),
398        None => iri.to_owned(),
399    }
400}
401
402/// Apply one inline term map to the context being built.
403fn apply_term_map(
404    result: &mut ActiveContext,
405    map: &Map<String, Value>,
406    session: &mut Session<'_>,
407) -> Result<(), Error> {
408    if let Some(base) = map.get("@base") {
409        match base {
410            Value::Null => result.base = None,
411            Value::String(value) => result.base = Some(value.clone()),
412            _ => return Err(Error::InvalidContext),
413        }
414    }
415    if let Some(vocab) = map.get("@vocab") {
416        match vocab {
417            Value::Null => result.vocab = None,
418            // `@vocab` may itself be a term or a compact IRI; the
419            // ActivityStreams context uses the blank-node prefix `_:`.
420            Value::String(value) => {
421                result.vocab = expand_iri(result, value, true, true);
422            }
423            _ => return Err(Error::InvalidContext),
424        }
425    }
426    if let Some(language) = map.get("@language") {
427        match language {
428            Value::Null => result.language = None,
429            Value::String(value) => result.language = Some(value.to_lowercase()),
430            _ => return Err(Error::InvalidContext),
431        }
432    }
433
434    let protected = map
435        .get("@protected")
436        .and_then(Value::as_bool)
437        .unwrap_or(false);
438    let mut defined = BTreeMap::new();
439    for key in map.keys() {
440        if is_keyword(key) {
441            continue;
442        }
443        create_term_definition(result, map, key, &mut defined, protected, session)?;
444    }
445    Ok(())
446}
447
448/// The JSON-LD "Create Term Definition" algorithm.
449///
450/// `defined` tracks terms already built and terms currently being built, which
451/// is what lets a term map define `"Emoji": "toot:Emoji"` *before* it defines
452/// `"toot"` — as litepub's context does — without depending on key order.
453fn create_term_definition(
454    active: &mut ActiveContext,
455    local: &Map<String, Value>,
456    term: &str,
457    defined: &mut BTreeMap<String, bool>,
458    protected: bool,
459    session: &mut Session<'_>,
460) -> Result<(), Error> {
461    match defined.get(term) {
462        Some(true) => return Ok(()),
463        Some(false) => return Err(Error::CyclicContext(term.to_owned())),
464        None => {}
465    }
466    if active.terms.len() >= session.limits.max_terms {
467        return Err(Error::TermBudgetExceeded);
468    }
469    defined.insert(term.to_owned(), false);
470
471    let value = local.get(term).unwrap_or(&Value::Null);
472    let mut definition = TermDefinition {
473        protected,
474        ..TermDefinition::default()
475    };
476
477    match value {
478        // `"term": null` removes the term; keys using it are dropped.
479        Value::Null => {}
480        Value::String(iri) => {
481            definition.iri =
482                expand_iri_while_defining(active, local, iri, defined, protected, session)?;
483            definition.prefix = ends_with_gen_delim(iri);
484        }
485        Value::Object(map) => {
486            if map.get("@id").is_some_and(Value::is_null) {
487                // An explicit null `@id` is the object form of removing a term.
488                Arc::make_mut(&mut active.terms).insert(term.to_owned(), definition);
489                defined.insert(term.to_owned(), true);
490                return Ok(());
491            }
492            if let Some(Value::Bool(flag)) = map.get("@protected") {
493                definition.protected = *flag;
494            }
495            if let Some(reverse) = map.get("@reverse") {
496                let Value::String(iri) = reverse else {
497                    return Err(Error::InvalidTermDefinition(term.to_owned()));
498                };
499                definition.iri =
500                    expand_iri_while_defining(active, local, iri, defined, protected, session)?;
501                definition.reverse = true;
502            } else if let Some(id) = map.get("@id") {
503                let Value::String(iri) = id else {
504                    return Err(Error::InvalidTermDefinition(term.to_owned()));
505                };
506                definition.iri =
507                    expand_iri_while_defining(active, local, iri, defined, protected, session)?;
508            } else {
509                // No `@id`: the term expands on its own, as a compact IRI if it
510                // looks like one, otherwise against `@vocab`.
511                definition.iri =
512                    expand_iri_while_defining(active, local, term, defined, protected, session)?;
513            }
514
515            if let Some(kind) = map.get("@type") {
516                let Value::String(value) = kind else {
517                    return Err(Error::InvalidTermDefinition(term.to_owned()));
518                };
519                definition.type_mapping = Some(match value.as_str() {
520                    "@id" => TypeMapping::Id,
521                    "@vocab" => TypeMapping::Vocab,
522                    "@json" => TypeMapping::Json,
523                    "@none" => TypeMapping::None,
524                    other => TypeMapping::Datatype(
525                        expand_iri_while_defining(
526                            active, local, other, defined, protected, session,
527                        )?
528                        .unwrap_or_else(|| other.to_owned()),
529                    ),
530                });
531            }
532
533            match map.get("@container") {
534                Some(Value::String(value)) => definition.container.add(value),
535                Some(Value::Array(values)) => {
536                    for value in values {
537                        let Value::String(value) = value else {
538                            return Err(Error::InvalidTermDefinition(term.to_owned()));
539                        };
540                        definition.container.add(value);
541                    }
542                }
543                Some(_) => return Err(Error::InvalidTermDefinition(term.to_owned())),
544                None => {}
545            }
546
547            match map.get("@language") {
548                Some(Value::Null) => definition.language = Some(None),
549                Some(Value::String(value)) => {
550                    definition.language = Some(Some(value.to_lowercase()));
551                }
552                Some(_) => return Err(Error::InvalidTermDefinition(term.to_owned())),
553                None => {}
554            }
555
556            if let Some(Value::Bool(flag)) = map.get("@prefix") {
557                definition.prefix = *flag;
558            }
559            if let Some(scoped) = map.get("@context") {
560                definition.scoped = Some(Box::new(scoped.clone()));
561            }
562        }
563        _ => return Err(Error::InvalidTermDefinition(term.to_owned())),
564    }
565
566    Arc::make_mut(&mut active.terms).insert(term.to_owned(), definition);
567    defined.insert(term.to_owned(), true);
568    Ok(())
569}
570
571/// The JSON-LD "IRI Expansion" algorithm, as used while *building* a context.
572///
573/// This is the variant that may define other terms as a side effect: a term map
574/// is a set of mutually referring definitions, not an ordered list, so
575/// `"Emoji": "toot:Emoji"` must work even though litepub's context defines
576/// `"toot"` several lines further down.
577fn expand_iri_while_defining(
578    active: &mut ActiveContext,
579    local: &Map<String, Value>,
580    value: &str,
581    defined: &mut BTreeMap<String, bool>,
582    protected: bool,
583    session: &mut Session<'_>,
584) -> Result<Option<String>, Error> {
585    if is_keyword(value) {
586        return Ok(Some(value.to_owned()));
587    }
588    if value.starts_with('@') {
589        return Ok(None);
590    }
591
592    if local.contains_key(value) && defined.get(value) != Some(&true) {
593        create_term_definition(active, local, value, defined, protected, session)?;
594    }
595    if let Some(definition) = active.term(value) {
596        return Ok(definition.iri.clone());
597    }
598
599    if let Some(index) = value.find(':')
600        && index > 0
601    {
602        let (prefix, rest) = value.split_at(index);
603        let suffix = &rest[1..];
604        if prefix == "_" || suffix.starts_with("//") {
605            return Ok(Some(value.to_owned()));
606        }
607        if local.contains_key(prefix) && defined.get(prefix) != Some(&true) {
608            create_term_definition(active, local, prefix, defined, protected, session)?;
609        }
610        if let Some(definition) = active.term(prefix)
611            && definition.prefix
612            && let Some(iri) = &definition.iri
613        {
614            let mut expanded = iri.clone();
615            expanded.push_str(suffix);
616            return Ok(Some(expanded));
617        }
618        return Ok(Some(value.to_owned()));
619    }
620
621    if let Some(prefix) = active.vocab() {
622        let mut expanded = prefix.to_owned();
623        expanded.push_str(value);
624        return Ok(Some(expanded));
625    }
626    Ok(Some(value.to_owned()))
627}
628
629/// The JSON-LD "IRI Expansion" algorithm, as used while *reading* a document.
630///
631/// Returns `None` when the value expands to nothing: a term mapped to null, or
632/// an unrecognised `@`-prefixed key. Both are dropped rather than carried
633/// through, so an invented keyword cannot arrive as data.
634pub(crate) fn expand_iri(
635    active: &ActiveContext,
636    value: &str,
637    vocab: bool,
638    document_relative: bool,
639) -> Option<String> {
640    if is_keyword(value) {
641        return Some(value.to_owned());
642    }
643    if value.starts_with('@') {
644        return None;
645    }
646
647    if vocab && let Some(definition) = active.term(value) {
648        return definition.iri.clone();
649    }
650
651    if let Some(index) = value.find(':')
652        && index > 0
653    {
654        let (prefix, rest) = value.split_at(index);
655        let suffix = &rest[1..];
656        if prefix == "_" || suffix.starts_with("//") {
657            return Some(value.to_owned());
658        }
659        if let Some(definition) = active.term(prefix)
660            && definition.prefix
661            && let Some(iri) = &definition.iri
662        {
663            let mut expanded = iri.clone();
664            expanded.push_str(suffix);
665            return Some(expanded);
666        }
667        return Some(value.to_owned());
668    }
669
670    if vocab && let Some(prefix) = active.vocab() {
671        let mut expanded = prefix.to_owned();
672        expanded.push_str(value);
673        return Some(expanded);
674    }
675    if document_relative && let Some(base) = active.base() {
676        return Some(resolve_against(base, value));
677    }
678    Some(value.to_owned())
679}
680
681/// Whether `value` has a scheme, i.e. is not a relative reference.
682pub(crate) fn is_absolute_iri(value: &str) -> bool {
683    let Some(index) = value.find(':') else {
684        return false;
685    };
686    if index == 0 {
687        return false;
688    }
689    let scheme = &value[..index];
690    scheme.starts_with(|c: char| c.is_ascii_alphabetic())
691        && scheme
692            .chars()
693            .all(|c| c.is_ascii_alphanumeric() || matches!(c, '+' | '-' | '.'))
694}
695
696/// Resolve `reference` against `base` per RFC 3986, falling back to the
697/// reference itself when either side is not a usable IRI.
698pub(crate) fn resolve_against(base: &str, reference: &str) -> String {
699    use iri_string::types::{IriAbsoluteStr, IriReferenceStr};
700
701    let Ok(base) = IriAbsoluteStr::new(base) else {
702        return reference.to_owned();
703    };
704    let Ok(reference) = IriReferenceStr::new(reference) else {
705        return reference.to_owned();
706    };
707    reference.resolve_against(base).to_string()
708}
ojak_jsonld/context.rs

ojak_jsonld/
context.rs
