jsonld_context_processing/
stack.rs

1use std::sync::Arc;
2
3/// Maximum depth of the remote context chain.
4///
5/// The [context processing algorithm][1] mandates a processor-defined limit
6/// on the number of entries in the `remote contexts` array; exceeding it is a
7/// `context overflow` error. This bounds the damage a hostile loader can do
8/// by serving an endless chain of distinct context IRIs.
9///
10/// [1]: <https://www.w3.org/TR/json-ld11-api/#context-processing-algorithm>
11pub const MAX_REMOTE_CONTEXTS: usize = 64;
12
13/// Single frame of the context processing stack.
14struct StackNode<I> {
15    /// Previous frame.
16    previous: Option<Arc<StackNode<I>>>,
17
18    /// URL of the last loaded context.
19    url: I,
20}
21
22impl<I> StackNode<I> {
23    /// Creates a stack frame recording the load of `url` on top of `previous`.
24    fn new(previous: Option<Arc<StackNode<I>>>, url: I) -> StackNode<I> {
25        StackNode { previous, url }
26    }
27
28    /// Checks whether this frame or any frame below it holds `url`.
29    fn contains(&self, url: &I) -> bool
30    where
31        I: PartialEq,
32    {
33        if self.url == *url {
34            true
35        } else {
36            match &self.previous {
37                Some(prev) => prev.contains(url),
38                None => false,
39            }
40        }
41    }
42}
43
44/// The chain of remote context URLs currently being processed.
45///
46/// This is the specification's `remote contexts` array. It serves two purposes:
47/// spotting a context that includes itself, and bounding the length of a remote
48/// context chain at [`MAX_REMOTE_CONTEXTS`]. Whether it is empty also tells the
49/// algorithm whether the context being processed came from a remote document,
50/// which is what decides if its `@base` entry applies.
51///
52/// Implemented as an immutable singly-linked list behind [`Arc`]s, so the copy
53/// each recursive call receives is a pointer bump rather than a clone of the
54/// chain.
55#[derive(Clone)]
56pub struct ProcessingStack<I> {
57    head: Option<Arc<StackNode<I>>>,
58}
59
60impl<I> ProcessingStack<I> {
61    /// Creates an empty stack, meaning no remote context is being processed.
62    #[must_use]
63    pub fn new() -> Self {
64        Self { head: None }
65    }
66
67    /// Checks whether no remote context has been entered, i.e. the context being
68    /// processed is not itself remote.
69    #[must_use]
70    pub fn is_empty(&self) -> bool {
71        self.head.is_none()
72    }
73
74    /// Returns the number of remote contexts on the stack.
75    ///
76    /// Walks the chain, so this is linear in the stack depth.
77    #[must_use]
78    pub fn len(&self) -> usize {
79        let mut len = 0;
80        let mut node = &self.head;
81        while let Some(frame) = node {
82            len += 1;
83            node = &frame.previous;
84        }
85        len
86    }
87
88    /// Checks whether `url` is already on the stack, meaning entering it would
89    /// close a loop.
90    pub fn cycle(&self, url: &I) -> bool
91    where
92        I: PartialEq,
93    {
94        match &self.head {
95            Some(head) => head.contains(url),
96            None => false,
97        }
98    }
99
100    /// Pushes `url` onto the stack, unless it is already there.
101    ///
102    /// Returns `true` when the URL was added, and `false` when it was already on
103    /// the stack and nothing changed. What `false` means is version-dependent:
104    /// JSON-LD 1.0 treats it as a recursive context inclusion error, while 1.1
105    /// simply skips reprocessing the context.
106    pub fn push(&mut self, url: I) -> bool
107    where
108        I: PartialEq,
109    {
110        if self.cycle(&url) {
111            false
112        } else {
113            let mut head = None;
114            std::mem::swap(&mut head, &mut self.head);
115            self.head = Some(Arc::new(StackNode::new(head, url)));
116            true
117        }
118    }
119}
120
121impl<I> Default for ProcessingStack<I> {
122    fn default() -> Self {
123        Self::new()
124    }
125}
jsonld_context_processing/stack.rs

jsonld_context_processing/
stack.rs
