structured_pades/document/
graph.rs

1//! One historical indirect graph, using stable indices and flat ownership.
2
3use super::{Document, Reading};
4use crate::arena::{Kind, NodeId};
5use crate::error::{Error, ErrorKind, ReadFailure, Syntax};
6use crate::model::admit;
7use crate::object::Object;
8use crate::range::{RangeSource, Stamp};
9use structured_asn1::memory::{HashWork, Memory, MemoryError, OwnedMap, OwnedVec, Work};
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
12pub(crate) struct Key {
13    pub(crate) number: u64,
14    pub(crate) generation: u16,
15}
16
17impl HashWork for Key {
18    fn hash_work(&self) -> Result<u64, MemoryError> {
19        Ok(2)
20    }
21}
22
23pub(crate) struct Node<'s, D, G> {
24    pub(crate) key: Key,
25    pub(crate) reading: Option<Reading<'s, D, G>>,
26    source: Option<usize>,
27}
28
29struct Cached {
30    bytes: OwnedVec<u8>,
31    body: structured_asn1::Span,
32    slots: OwnedVec<super::members::Slot>,
33}
34
35/// Full indirect closure of a historical catalog, including null references.
36/// Backlinks do not recurse or create reference-counted ownership cycles.
37pub struct Graph<'s, D, G> {
38    pub(crate) stamp: Stamp<D, G>,
39    pub(crate) revision: usize,
40    pub(crate) nodes: OwnedVec<Node<'s, D, G>, Memory>,
41    pub(crate) index: OwnedMap<Key, usize, Memory>,
42    pub(crate) session: &'s crate::Session,
43    streams: OwnedVec<Cached>,
44}
45
46impl<'s, D: Copy + Eq, G: Copy + Eq> Graph<'s, D, G> {
47    pub(crate) fn decoded(&self, owner: usize) -> Option<&[u8]> {
48        let node = &self.nodes[owner];
49        match node.source {
50            Some(index) => Some(&self.streams[index].bytes),
51            None => node
52                .reading
53                .as_ref()
54                .and_then(|reading| reading.decoded.as_deref()),
55        }
56    }
57    /// Immutable original file identity used for the complete closure.
58    #[must_use]
59    pub fn stamp(&self) -> Stamp<D, G> {
60        self.stamp
61    }
62    /// Historical ordinal used for every indirect resolution.
63    #[must_use]
64    pub fn revision(&self) -> usize {
65        self.revision
66    }
67    /// Actual historical catalog root, without cloning its parsed model.
68    ///
69    /// # Panics
70    /// Panics if the completed graph loses its validated catalog owner.
71    #[must_use]
72    pub fn root(&self) -> GraphObject<'_, 's, D, G> {
73        let reading = self.nodes[0].reading.as_ref().expect("validated catalog");
74        GraphObject {
75            graph: self,
76            owner: 0,
77            node: reading.value.root,
78        }
79    }
80}
81
82/// A node inside the actual graph owner. Resolution cannot substitute a node
83/// from another revision or silently use a newer generation's definition.
84#[derive(Clone, Copy)]
85pub struct GraphObject<'a, 's, D, G> {
86    pub(crate) graph: &'a Graph<'s, D, G>,
87    pub(crate) owner: usize,
88    pub(crate) node: NodeId,
89}
90
91impl<'a, 's, D: Copy + Eq, G: Copy + Eq> GraphObject<'a, 's, D, G> {
92    /// Direct value metadata and paid scalar queries use the same object core.
93    ///
94    /// # Panics
95    /// Panics if an internally issued graph object loses its owning reading.
96    #[must_use]
97    pub fn direct(self) -> Object<'a, 's, D, G> {
98        Object {
99            owner: &self.graph.nodes[self.owner]
100                .reading
101                .as_ref()
102                .expect("graph object owner")
103                .value,
104            node: self.node,
105        }
106    }
107
108    /// Original indirect owner identity, independent of this direct node.
109    #[must_use]
110    pub fn identity(self) -> (u64, u16) {
111        let key = self.graph.nodes[self.owner].key;
112        (key.number, key.generation)
113    }
114
115    /// Resolves a direct reference using the already completed graph index.
116    /// No I/O, parsing, fallback generation or retained-cache mutation occurs.
117    ///
118    /// # Panics
119    /// Panics if the completed reference-closure index omits an admitted reference.
120    pub fn resolved(self, operation: &impl Work) -> crate::Result<Option<Self>> {
121        let work = self.graph.session.query(operation);
122        let raw = self.direct();
123        admit(&work, raw.location(), 1)?;
124        let Some((number, generation)) = raw.reference() else {
125            return Ok(Some(self));
126        };
127        let index = self
128            .graph
129            .index
130            .get(&Key { number, generation }, &work)
131            .map_err(|cause| Error {
132                kind: ErrorKind::Resource(cause),
133                location: raw.location(),
134            })?
135            .copied()
136            .expect("complete reference closure");
137        Ok(self.graph.nodes[index]
138            .reading
139            .as_ref()
140            .map(|reading| Self {
141                graph: self.graph,
142                owner: index,
143                node: reading.value.root,
144            }))
145    }
146
147    /// Selects a dictionary field and resolves its actual original reference.
148    pub fn get(self, key: &[u8], operation: &impl Work) -> crate::Result<Option<Self>> {
149        let Some(node) = self.direct().get(key, operation)? else {
150            return Ok(None);
151        };
152        Self {
153            graph: self.graph,
154            owner: self.owner,
155            node: node.node,
156        }
157        .resolved(operation)
158    }
159
160    /// Visits direct array members with current admission before every step.
161    /// Returned objects can be resolved separately through this same graph.
162    pub fn members<'q>(self, operation: &'q impl Work) -> Option<GraphMembers<'a, 's, 'q, D, G>>
163    where
164        's: 'q,
165    {
166        Some(GraphMembers {
167            object: self,
168            members: self.direct().members(operation)?,
169        })
170    }
171}
172
173/// Paid fused direct member traversal using the existing linked-member core.
174pub struct GraphMembers<'a, 's, 'q, D, G> {
175    object: GraphObject<'a, 's, D, G>,
176    members: crate::object::Members<'a, 's, 'q, D, G>,
177}
178
179impl<'a, 's, D: Copy + Eq, G: Copy + Eq> Iterator for GraphMembers<'a, 's, '_, D, G> {
180    type Item = crate::Result<GraphObject<'a, 's, D, G>>;
181    fn next(&mut self) -> Option<Self::Item> {
182        self.members.next().map(|result| {
183            result.map(|node| GraphObject {
184                graph: self.object.graph,
185                owner: self.object.owner,
186                node: node.node,
187            })
188        })
189    }
190}
191impl<D: Copy + Eq, G: Copy + Eq> core::iter::FusedIterator for GraphMembers<'_, '_, '_, D, G> {}
192
193impl<'s, S: RangeSource> Document<'s, S> {
194    /// Resolves one complete historical closure with one cache per object stream.
195    ///
196    /// # Panics
197    /// Panics if an internally decoded root is not an object-stream member.
198    pub async fn graph<W: Work>(
199        &self,
200        revision: usize,
201        operation: &W,
202    ) -> Result<Graph<'s, S::Document, S::Generation>, ReadFailure<S::Error>> {
203        let work = self.session.query(operation);
204        let mut root = self.root(revision, &work).await?;
205        let location = root.value.root().location();
206        let key = Key {
207            number: root.number,
208            generation: root.generation,
209        };
210        let mut cache = StreamCache {
211            values: work.vector(),
212            index: work.map(),
213        };
214        let source = if let Some(bytes) = root.decoded.take() {
215            let Some(crate::xref::Target::Compressed { stream, .. }) =
216                self.target(revision, key.number, key.generation, &work)?
217            else {
218                unreachable!("a decoded root is an object-stream member")
219            };
220            Some(
221                cache
222                    .ensure(self, revision, stream, Some(bytes), location, &work)
223                    .await?,
224            )
225        } else {
226            None
227        };
228        let mut nodes = work.vector();
229        let mut index = work.map();
230        let resource = |cause| Error {
231            kind: ErrorKind::Resource(cause),
232            location,
233        };
234        index.try_insert(key, 0).map_err(resource)?;
235        nodes
236            .try_push(Node {
237                key,
238                reading: Some(root),
239                source,
240            })
241            .map_err(resource)?;
242        let mut at = 0;
243        while at < nodes.len() {
244            admit(&work, location, 1)?;
245            if nodes[at].reading.is_none() {
246                nodes[at] = cache
247                    .load(self, revision, nodes[at].key, location, &work)
248                    .await?;
249            }
250            // Move the owner out before growth, so discovery writes directly
251            // to the owning queue without another pending-node allocation.
252            if let Some(reading) = nodes[at].reading.take() {
253                discover(&reading, &mut nodes, &mut index, &work)?;
254                nodes[at].reading = Some(reading);
255            }
256            at += 1;
257        }
258        let graph = Graph {
259            stamp: self.stamp,
260            revision,
261            nodes: nodes.into_owned(),
262            index: index.into_owned(),
263            session: self.session,
264            streams: cache.values.into_owned(),
265        };
266        graph.validate(location, &work)?;
267        self.check(&work, location)?;
268        Ok(graph)
269    }
270}
271
272struct StreamCache<W: Work> {
273    values: OwnedVec<Cached, W>,
274    index: OwnedMap<Key, usize, W>,
275}
276impl<W: Work> StreamCache<W> {
277    async fn ensure<S: RangeSource>(
278        &mut self,
279        document: &Document<'_, S>,
280        revision: usize,
281        stream: u64,
282        bytes: Option<OwnedVec<u8>>,
283        location: crate::source::Location,
284        work: &W,
285    ) -> Result<usize, ReadFailure<S::Error>> {
286        let key = Key {
287            number: stream,
288            generation: 0,
289        };
290        let resource = |cause| Error {
291            kind: ErrorKind::Resource(cause),
292            location,
293        };
294        if let Some(&index) = self.index.get(&key, work).map_err(resource)? {
295            return Ok(index);
296        }
297        let container = document
298            .object(revision, stream, 0, work)
299            .await?
300            .ok_or(Error {
301                kind: ErrorKind::Syntax(Syntax::Object),
302                location,
303            })?;
304        let value = cached(document, container, bytes, revision, work).await?;
305        let index = self.values.len();
306        self.values.try_push(value).map_err(resource)?;
307        self.index.try_insert(key, index).map_err(resource)?;
308        Ok(index)
309    }
310
311    async fn load<'s, S: RangeSource>(
312        &mut self,
313        document: &Document<'s, S>,
314        revision: usize,
315        key: Key,
316        location: crate::source::Location,
317        work: &W,
318    ) -> Result<Node<'s, S::Document, S::Generation>, ReadFailure<S::Error>> {
319        if let Some(crate::xref::Target::Compressed { stream, index }) =
320            document.target(revision, key.number, key.generation, work)?
321        {
322            let ordinal = self
323                .ensure(document, revision, stream, None, location, work)
324                .await?;
325            let cache = &self.values[ordinal];
326            let slot = usize::try_from(index)
327                .ok()
328                .and_then(|index| cache.slots.get(index))
329                .ok_or(Error {
330                    kind: ErrorKind::Syntax(Syntax::Object),
331                    location,
332                })?;
333            if slot.number != key.number {
334                return Err(Error {
335                    kind: ErrorKind::Syntax(Syntax::Object),
336                    location,
337                }
338                .into());
339            }
340            let value = super::members::selected(
341                document.session,
342                document.stamp,
343                &cache.bytes,
344                cache.body,
345                slot,
346                revision,
347                work,
348            )
349            .await
350            .map_err(super::resolve::convert)?;
351            Ok(Node {
352                key,
353                reading: Some(Reading {
354                    value,
355                    decoded: None,
356                    stream: None,
357                    number: key.number,
358                    generation: key.generation,
359                    revision,
360                }),
361                source: Some(ordinal),
362            })
363        } else {
364            Ok(Node {
365                key,
366                reading: document
367                    .object(revision, key.number, key.generation, work)
368                    .await?,
369                source: None,
370            })
371        }
372    }
373}
374
375fn discover<'s, D, G, W: Work>(
376    reading: &Reading<'s, D, G>,
377    nodes: &mut OwnedVec<Node<'s, D, G>, W>,
378    index: &mut OwnedMap<Key, usize, W>,
379    work: &W,
380) -> crate::Result<()> {
381    for node in &reading.value.arena.nodes {
382        admit(work, node.location, 1)?;
383        if let Kind::Reference { number, generation } = node.kind {
384            let key = Key { number, generation };
385            let resource = |cause| Error {
386                kind: ErrorKind::Resource(cause),
387                location: node.location,
388            };
389            if index.get(&key, work).map_err(resource)?.is_none() {
390                index.try_insert(key, nodes.len()).map_err(resource)?;
391                nodes
392                    .try_push(Node {
393                        key,
394                        reading: None,
395                        source: None,
396                    })
397                    .map_err(resource)?;
398            }
399        }
400    }
401    Ok(())
402}
403
404impl<D: Copy + Eq, G: Copy + Eq> Graph<'_, D, G> {
405    fn validate(&self, location: crate::source::Location, work: &impl Work) -> crate::Result<()> {
406        let malformed = || Error {
407            kind: ErrorKind::Syntax(Syntax::Trailer),
408            location,
409        };
410        let reading = self
411            .nodes
412            .first()
413            .and_then(|node| node.reading.as_ref())
414            .ok_or_else(malformed)?;
415        if reading.stream.is_some() {
416            return Err(malformed());
417        }
418        let root = self.root();
419        if root.direct().kind() != crate::object::Type::Dictionary {
420            return Err(malformed());
421        }
422        let kind = root.get(b"Type", work)?.ok_or_else(malformed)?;
423        if !kind.direct().name_equals(b"Catalog", work)? {
424            return Err(malformed());
425        }
426        Ok(())
427    }
428}
429
430async fn cached<'s, S: RangeSource>(
431    document: &Document<'s, S>,
432    container: Reading<'s, S::Document, S::Generation>,
433    bytes: Option<OwnedVec<u8>>,
434    revision: usize,
435    work: &impl Work,
436) -> Result<Cached, ReadFailure<S::Error>> {
437    let (bytes, body, count, first) = if let Some(bytes) = bytes {
438        let prepared = document.stream_plan(&container, true, work).await?;
439        let (count, first) = prepared.layout.expect("object-stream controls");
440        (bytes, prepared.body, count, first)
441    } else {
442        let decoded = document.stream_data(&container, true, work).await?;
443        let (count, first) = decoded.layout.expect("object-stream controls");
444        (decoded.bytes, decoded.body, count, first)
445    };
446    let slots = super::members::directory(
447        document.session,
448        document.stamp,
449        &bytes,
450        body,
451        (count, first),
452        revision,
453        work,
454    )
455    .await
456    .map_err(super::resolve::convert)?;
457    Ok(Cached { bytes, body, slots })
458}
structured_pades/document/graph.rs

structured_pades/document/
graph.rs
