jsonld_context_processing/algorithm/

mod.rs

//! # Two implementations, one algorithm: keep `sync.rs` in step
//!
//! This module, together with `define.rs` and `iri.rs`, holds the `async`
//! implementation of the [context processing algorithm][1] — the one that can
//! call the [`Loader`] to fetch remote contexts and `@import`ed documents.
//! `sync.rs`, in this same directory, holds a second, hand-maintained
//! implementation of the *same* algorithm with `async`, `.await` and the boxed
//! [`Recursion`] stripped out and recursion made direct. It is used as a fast path whenever
//! `requires_loader` proves the input contains no remote `@context` IRI and no
//! `@import`, which is the common case in real payloads.
//!
//! Which of the two runs is invisible to callers: for any input both must
//! produce the same active context and the same error. **A change to the
//! algorithm here therefore has to be mirrored in `sync.rs`, and a change there
//! mirrored back here.** Nothing enforces this — the two are separate function
//! bodies with no shared code, so a fix applied to only one silently makes the
//! result depend on whether the input happened to reference a remote context.
//! The mirrored pairs are:
//!
//! | this module | `sync.rs` |
//! |---|---|
//! | `process_context` (`mod.rs`) | `process_context_sync` |
//! | `define` (`define.rs`) | `define_sync` |
//! | `expand_iri_with` (`iri.rs`) | `expand_iri_with_sync` |
//!
//! `sync.rs` does guard the one class of divergence it can detect — reaching a
//! code path that would need the loader — by returning
//! [`Error::LoadingDocumentFailed`]. That protects against `requires_loader`
//! drifting out of step with the algorithm body; it says nothing about the two
//! implementations otherwise agreeing.
//!
//! [1]: https://www.w3.org/TR/json-ld11-api/#context-processing-algorithm

use std::{hash::Hash, sync::Arc};

use crate::{Error, Options, Process, Processed, ProcessingCache, ProcessingResult, ProcessingStack, WarningHandler, cache::cache_key};
use iri_rs::{Iri, IriBuf};
use jsonld_core::{Context, Environment, ExtractContext, Loader, ProcessingMode, Term};
use jsonld_syntax::{self as syntax, Nullable};
use rdfx::vocabulary::VocabularyMut;

mod define;
mod iri;
mod merged;
mod native_stack;
mod sync;

pub use define::*;
pub use iri::*;
pub use merged::*;
use native_stack::Recursion;
use sync::{process_context_sync, requires_loader};
use syntax::context::definition::KeyOrKeywordRef;

/// Checks an `@vocab` value against the JSON-LD 1.0 rule.
///
/// 1.0 required the value to be an absolute IRI or a blank node identifier;
/// document-relative resolution only arrived in 1.1. A bare `_:` prefix counts,
/// as it is what makes `@vocab` map properties to blank nodes.
pub(crate) fn is_valid_vocab_json_ld_1_0(value: &syntax::context::definition::Vocab) -> bool {
    value.as_str().starts_with("_:") || Iri::new(value.as_str()).is_ok()
}

impl Process for syntax::context::Context {
    async fn process_full<N, L, W>(
        &self,
        vocabulary: &mut N,
        active_context: &Context<N::Iri, N::BlankId>,
        loader: &L,
        base_url: Option<N::Iri>,
        options: Options,
        mut warnings: W,
    ) -> Result<Processed<'_, N::Iri, N::BlankId>, Error<L::Error>>
    where
        N: VocabularyMut,
        N::Iri: Clone + Eq + Hash,
        N::BlankId: Clone + PartialEq,
        L: Loader,
        W: WarningHandler<N>,
    {
        // Fast path: no remote `@context` IRIs and no `@import` anywhere in
        // the tree means the entire algorithm runs synchronously — no
        // boxed `Recursion` per level, no future state machine.
        if !requires_loader(self) {
            return process_context_sync(
                Environment {
                    vocabulary,
                    loader,
                    warnings: &mut warnings,
                },
                active_context,
                self,
                ProcessingStack::default(),
                base_url,
                options,
                0,
            );
        }

        process_context(
            Environment {
                vocabulary,
                loader,
                warnings: &mut warnings,
            },
            active_context,
            self,
            ProcessingStack::default(),
            base_url,
            options,
            true,
        )
        .await
    }

    async fn process_full_with_cache<N, L, W>(
        &self,
        vocabulary: &mut N,
        active_context: &Context<N::Iri, N::BlankId>,
        loader: &L,
        base_url: Option<N::Iri>,
        options: Options,
        mut warnings: W,
        cache: &ProcessingCache<N::Iri, N::BlankId>,
    ) -> Result<Processed<'_, N::Iri, N::BlankId>, Error<L::Error>>
    where
        N: VocabularyMut,
        N::Iri: Clone + Eq + Hash,
        N::BlankId: Clone + Eq + Hash,
        L: Loader,
        W: WarningHandler<N>,
    {
        let key = cache_key(active_context, self, base_url.as_ref(), options);

        if let Some(cached) = cache.get(key, active_context, self, base_url.as_ref(), options) {
            return Ok(Processed::new(self, (*cached).clone()));
        }

        // Retained for the cache entry: `base_url` is moved into processing.
        let entry_active = active_context.clone();
        let entry_base_url = base_url.clone();

        let processed = if requires_loader(self) {
            process_context(
                Environment {
                    vocabulary,
                    loader,
                    warnings: &mut warnings,
                },
                active_context,
                self,
                ProcessingStack::default(),
                base_url,
                options,
                true,
            )
            .await?
        } else {
            process_context_sync(
                Environment {
                    vocabulary,
                    loader,
                    warnings: &mut warnings,
                },
                active_context,
                self,
                ProcessingStack::default(),
                base_url,
                options,
                0,
            )?
        };

        cache.insert(key, entry_active, self.clone(), entry_base_url, options, Arc::new(processed.processed.clone()));
        Ok(processed)
    }
}

/// Resolves `iri_ref` against `base_iri` and interns the result in `vocabulary`.
///
/// With no base IRI, `iri_ref` must already be an absolute IRI. Returns `None`
/// when the reference cannot be turned into one either way.
fn resolve_iri<V, I>(vocabulary: &mut V, iri_ref: iri_rs::IriRef<&str>, base_iri: Option<&I>) -> Option<I>
where
    V: rdfx::vocabulary::IriVocabularyMut<Iri = I>,
{
    if let Some(base_iri) = base_iri {
        let base = vocabulary.iri(base_iri)?;
        let resolved = iri_ref.resolved(&base).ok()?;
        let iri_buf = IriBuf::try_from(resolved).ok()?;
        Some(vocabulary.insert_owned(iri_buf))
    } else {
        let iri = Iri::try_from(iri_ref).ok()?;
        Some(vocabulary.insert(iri))
    }
}

/// Runs the [context processing algorithm][1], layering `local_context` on top
/// of `active_context`.
///
/// Recurses for each remote `@context` IRI, fetching it through the loader, and
/// for each term definition's scoped `@context` via `define`. `remote_contexts`
/// carries the chain of remote context URLs entered so far, which bounds that
/// recursion; a top-level call starts from an empty [`ProcessingStack`].
///
/// `validate_scoped_context` is the algorithm's input of the same name: `true`
/// for a document's own `@context` and for contexts applied while expanding,
/// `false` only when Create Term Definition validates a scoped `@context`
/// (step 21.3). Only then is a context already in `remote_contexts` skipped
/// (step 5.2.2); anywhere else a repeat is processed again, because JSON-LD
/// processes the entries of a `@context` array in order.
///
/// Every mutation is applied to a clone of `active_context`, so the caller's
/// context is left untouched.
///
/// This is the `async` half of a mirrored pair; see the module documentation
/// before changing it.
///
/// [1]: https://www.w3.org/TR/json-ld11-api/#context-processing-algorithm
async fn process_context<'l: 'a, 'a, N, L, W>(
    mut env: Environment<'a, N, L, W>,
    active_context: &'a Context<N::Iri, N::BlankId>,
    local_context: &'l syntax::context::Context,
    mut remote_contexts: ProcessingStack<N::Iri>,
    base_url: Option<N::Iri>,
    mut options: Options,
    validate_scoped_context: bool,
) -> ProcessingResult<'l, N::Iri, N::BlankId, L::Error>
where
    N: VocabularyMut,
    N::Iri: Clone + Eq + Hash,
    N::BlankId: Clone + PartialEq,
    L: Loader,
    W: WarningHandler<N>,
{
    // 1) Initialize result to the result of cloning active context.
    let mut result = active_context.clone();
    result.set_processing_mode(options.processing_mode);

    // 2) If `local_context` is an object containing the member @propagate,
    // its value MUST be boolean true or false, set `propagate` to that value.
    if let syntax::context::Context::One(syntax::ContextEntry::Definition(def)) = local_context
        && let Some(propagate) = def.propagate
    {
        if options.processing_mode == ProcessingMode::JsonLd1_0 {
            return Err(Error::InvalidContextEntry);
        }

        options.propagate = propagate;
    }

    // 3) If propagate is false, and result does not have a previous context,
    // set previous context in result to active context.
    if !options.propagate && result.previous_context().is_none() {
        result.set_previous_context(active_context.clone());
    }

    // 4) If local context is not an array, set it to an array containing only local context.
    // 5) For each item context in local context:
    for context in local_context {
        match context {
            // 5.1) If context is null:
            syntax::ContextEntry::Null => {
                // If `override_protected` is false and `active_context` contains any protected term
                // definitions, an invalid context nullification has been detected and processing
                // is aborted.
                if !options.override_protected && result.has_protected_items() {
                    return Err(Error::InvalidContextNullification);
                }
                // Otherwise, initialize result as a newly-initialized active context, setting
                // previous_context in result to the previous value of result if propagate is
                // false. Continue with the next context.
                let previous_result = result;

                // Initialize `result` as a newly-initialized active context, setting both
                // `base_iri` and `original_base_url` to the value of `original_base_url` in
                // active context, ...
                result = Context::new(active_context.original_base_url().cloned());
                result.set_processing_mode(options.processing_mode);

                // ... and, if `propagate` is `false`, `previous_context` in `result` to the
                // previous value of `result`.
                if !options.propagate {
                    result.set_previous_context(previous_result);
                }
            }

            // 5.2) If context is a string,
            syntax::ContextEntry::IriRef(iri_ref) => {
                // Initialize `context` to the result of resolving context against base URL.
                // If base URL is not a valid IRI, then context MUST be a valid IRI, otherwise
                // a loading document failed error has been detected and processing is aborted.
                let context_iri = resolve_iri(env.vocabulary, iri_ref.as_ref(), base_url.as_ref()).ok_or(Error::LoadingDocumentFailed)?;

                // 5.2.2) If validate scoped context is false, and remote contexts already
                // includes context do not process context further and continue to any next
                // context in local context.
                //
                // JSON-LD 1.0 had no such allowance: a context already in remote contexts is a
                // recursive context inclusion error, whatever the caller.
                if remote_contexts.cycle(&context_iri) {
                    if options.processing_mode == ProcessingMode::JsonLd1_0 {
                        return Err(Error::RecursiveContextInclusion);
                    }
                    if !validate_scoped_context {
                        continue;
                    }
                }

                // 5.2.3) If the number of entries in the `remote_contexts` array exceeds a
                // processor defined limit, a context overflow error has been detected and
                // processing is aborted; otherwise, add context to remote contexts.
                if remote_contexts.len() >= crate::MAX_REMOTE_CONTEXTS {
                    return Err(Error::ContextOverflow);
                }
                remote_contexts.enter(context_iri.clone());

                // 5.2.4) If context was previously dereferenced, then the processor MUST NOT do a
                // further dereference, and context is set to the previously established internal
                // representation: set `context_document` to the previously dereferenced document,
                // and set loaded context to the value of the @context entry from the document in
                // context document.
                //
                // 5.2.5) Otherwise, set `context document` to the RemoteDocument obtained by
                // dereferencing context using the LoadDocumentCallback, passing context for url,
                // and http://www.w3.org/ns/json-ld#context for profile and for requestProfile.
                //
                // If context cannot be dereferenced, or the document from context document cannot
                // be transformed into the internal representation , a loading remote context
                // failed error has been detected and processing is aborted.
                // If the document has no top-level map with an @context entry, an invalid remote
                // context has been detected and processing is aborted.
                // Set loaded context to the value of that entry.
                let loaded_context = if let Some(previously) = remote_contexts.dereferenced(&context_iri) {
                    previously
                } else {
                    let loaded = Arc::new(
                        env.loader
                            .load_with(env.vocabulary, context_iri.clone())
                            .await?
                            .into_document()
                            .into_ld_context()
                            .map_err(Error::ContextExtractionFailed)?,
                    );
                    remote_contexts.remember_dereferenced(context_iri.clone(), Arc::clone(&loaded));
                    loaded
                };

                // 5.2.6) Set result to the result of recursively calling this algorithm, passing
                // result for active context, loaded context for local context, the documentUrl of
                // context document for base URL, a copy of remote contexts, and validate scoped
                // context.
                let new_options = Options {
                    processing_mode: options.processing_mode,
                    override_protected: false,
                    propagate: true,
                    vocab: options.vocab,
                };

                let r = Recursion::new(process_context(
                    Environment {
                        vocabulary: env.vocabulary,
                        loader: env.loader,
                        warnings: env.warnings,
                    },
                    &result,
                    &loaded_context,
                    remote_contexts.clone(),
                    Some(context_iri),
                    new_options,
                    validate_scoped_context,
                ))
                .await?;

                result = r.into_processed();
            }

            // 5.4) Context definition.
            syntax::ContextEntry::Definition(context) => {
                // 5.5) If context has a @version entry:
                if context.version.is_some() {
                    // 5.5.2) If processing mode is set to json-ld-1.0, a processing mode conflict
                    // error has been detected.
                    if options.processing_mode == ProcessingMode::JsonLd1_0 {
                        return Err(Error::ProcessingModeConflict);
                    }
                }

                // 5.6) If context has an @import entry:
                let import_context = match &context.import {
                    Some(import_value) => {
                        // 5.6.1) If processing mode is json-ld-1.0, an invalid context entry error
                        // has been detected.
                        if options.processing_mode == ProcessingMode::JsonLd1_0 {
                            return Err(Error::InvalidContextEntry);
                        }

                        // 5.6.3) Initialize import to the result of resolving the value of
                        // @import.
                        let import = resolve_iri(env.vocabulary, import_value.as_ref(), base_url.as_ref()).ok_or(Error::InvalidImportValue)?;

                        // 5.6.4) Dereference import.
                        let import_context = env
                            .loader
                            .load_with(env.vocabulary, import.clone())
                            .await?
                            .into_document()
                            .into_ld_context()
                            .map_err(Error::ContextExtractionFailed)?;

                        // If the dereferenced document has no top-level map with an @context
                        // entry, or if the value of @context is not a context definition
                        // (i.e., it is not an map), an invalid remote context has been
                        // detected and processing is aborted; otherwise, set import context
                        // to the value of that entry.
                        match &import_context {
                            syntax::context::Context::One(syntax::ContextEntry::Definition(import_context_def)) => {
                                // If `import_context` has a @import entry, an invalid context entry
                                // error has been detected and processing is aborted.
                                if import_context_def.import.is_some() {
                                    return Err(Error::InvalidContextEntry);
                                }
                            }
                            _ => {
                                return Err(Error::InvalidRemoteContext);
                            }
                        }

                        // Set `context` to the result of merging context into
                        // `import_context`, replacing common entries with those from
                        // `context`.
                        Some(import_context)
                    }
                    None => None,
                };

                let context = Merged::new(context, import_context);

                // 5.7) If context has a @base entry and remote contexts is empty, i.e.,
                // the currently being processed context is not a remote context:
                if remote_contexts.is_empty() {
                    // Initialize value to the value associated with the @base entry.
                    if let Some(value) = context.base() {
                        match value {
                            syntax::Nullable::Null => {
                                // If value is null, remove the base IRI of result.
                                result.set_base_iri(None);
                            }
                            syntax::Nullable::Some(iri_ref) => {
                                if let Ok(iri) = Iri::try_from(iri_ref.as_ref()) {
                                    result.set_base_iri(Some(env.vocabulary.insert(iri)));
                                } else {
                                    let resolved = resolve_iri(env.vocabulary, iri_ref.as_ref(), result.base_iri()).ok_or(Error::InvalidBaseIri)?;
                                    result.set_base_iri(Some(resolved));
                                }
                            }
                        }
                    }
                }

                // 5.8) If context has a @vocab entry:
                // Initialize value to the value associated with the @vocab entry.
                if let Some(value) = context.vocab() {
                    match value {
                        syntax::Nullable::Null => {
                            // If value is null, remove any vocabulary mapping from result.
                            result.set_vocabulary(None);
                        }
                        syntax::Nullable::Some(value) => {
                            // Otherwise, if value is an IRI or blank node identifier, the
                            // vocabulary mapping of result is set to the result of IRI
                            // expanding value using true for document relative. If it is not
                            // an IRI, or a blank node identifier, an invalid vocab mapping
                            // error has been detected and processing is aborted.
                            // NOTE: The use of blank node identifiers to value for @vocab is
                            // obsolete, and may be removed in a future version of JSON-LD.
                            //
                            // Document-relative expansion of `@vocab` is a JSON-LD 1.1 addition:
                            // 1.0 required an absolute IRI or blank node identifier, and rejects
                            // `""` and `/relative` (`expand#t0115`, `expand#t0116`). A bare `_:`
                            // prefix stays valid in 1.0 (`expand#t0075`).
                            let json_ld_1_0 = options.processing_mode == ProcessingMode::JsonLd1_0;
                            if json_ld_1_0 && !is_valid_vocab_json_ld_1_0(value) {
                                return Err(Error::InvalidVocabMapping);
                            }

                            match expand_iri_simple(&mut env, &result, Nullable::Some(value.into()), !json_ld_1_0, Some(options.vocab))? {
                                Some(arc) if matches!(arc.as_ref(), Term::Id(_)) => {
                                    let term = std::sync::Arc::try_unwrap(arc).unwrap_or_else(|a| (*a).clone());
                                    result.set_vocabulary(Some(term));
                                }
                                _ => return Err(Error::InvalidVocabMapping),
                            }
                        }
                    }
                }

                // 5.9) If context has a @language entry:
                if let Some(value) = context.language() {
                    match value {
                        Nullable::Null => {
                            // 5.9.2) If value is null, remove any default language from result.
                            result.set_default_language(None);
                        }
                        Nullable::Some(tag) => {
                            result.set_default_language(Some(tag.to_owned()));
                        }
                    }
                }

                // 5.10) If context has a @direction entry:
                if let Some(value) = context.direction() {
                    // 5.10.1) If processing mode is json-ld-1.0, an invalid context entry error
                    // has been detected and processing is aborted.
                    if options.processing_mode == ProcessingMode::JsonLd1_0 {
                        return Err(Error::InvalidContextEntry);
                    }

                    match value {
                        Nullable::Null => {
                            // 5.10.3) If value is null, remove any base direction from result.
                            result.set_default_base_direction(None);
                        }
                        Nullable::Some(dir) => {
                            result.set_default_base_direction(Some(dir));
                        }
                    }
                }

                // 5.12) Create a map `defined` to keep track of whether or not a term
                // has already been defined or is currently being defined during recursion.
                let mut defined = DefinedTerms::new();
                let protected = context.protected().unwrap_or(false);

                // 5.13) For each key-value pair in context where key is not
                // @base, @direction, @import, @language, @propagate, @protected, @version,
                // or @vocab,
                // invoke the Create Term Definition algorithm passing result for
                // active context, context for local context, key, defined, base URL,
                // and the value of the @protected entry from context, if any, for protected.
                // (and the value of override protected)
                if context.type_().is_some() {
                    define(
                        Environment {
                            vocabulary: env.vocabulary,
                            loader: env.loader,
                            warnings: env.warnings,
                        },
                        &mut result,
                        &context,
                        KeyOrKeywordRef::Keyword(syntax::Keyword::Type),
                        &mut defined,
                        remote_contexts.clone(),
                        base_url.clone(),
                        protected,
                        options,
                    )
                    .await?;
                }

                for (key, _binding) in context.bindings() {
                    define(
                        Environment {
                            vocabulary: env.vocabulary,
                            loader: env.loader,
                            warnings: env.warnings,
                        },
                        &mut result,
                        &context,
                        key.into(),
                        &mut defined,
                        remote_contexts.clone(),
                        base_url.clone(),
                        protected,
                        options,
                    )
                    .await?;
                }
            }
        }
    }

    Ok(Processed::new(local_context, result))
}