typst_pack/
package_catalog.rs

1//! Validated package input values.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5#[cfg(feature = "package-reading")]
6use typst::foundations::Bytes;
7use typst::syntax::package::{PackageSpec, PackageVersion};
8
9use crate::paths::{canonical_relative_path, path_tree_conflicts};
10use crate::payload::SharedBytes;
11use crate::{CanonicalIdentity, CanonicalIdentityRole};
12
13/// Whether a Package Tree's bytes travel inside the Pack or must be fulfilled
14/// externally when the Pack is compiled.
15#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
16pub enum PackageDisposition {
17    /// The tree's exact bytes are stored in the Pack.
18    Embedded,
19    /// The tree is declared and must be supplied at compilation.
20    External,
21}
22
23impl PackageDisposition {
24    /// Whether the tree's exact bytes are stored in the Pack.
25    pub fn is_embedded(self) -> bool {
26        matches!(self, Self::Embedded)
27    }
28}
29
30/// Every addressable regular file beneath one read package root.
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct PackageTree {
33    files: BTreeMap<String, SharedBytes>,
34    identity: CanonicalIdentity,
35    file_count: u64,
36    byte_length: u64,
37}
38
39impl PackageTree {
40    /// Constructs a tree by taking ownership of every file's exact bytes.
41    pub fn from_owned_entries(
42        entries: impl IntoIterator<Item = (impl AsRef<str>, Vec<u8>)>,
43    ) -> Result<Self, PackageTreeError> {
44        Self::from_shared_entries(
45            entries
46                .into_iter()
47                .map(|(path, data)| (path.as_ref().to_owned(), SharedBytes::new(data)))
48                .collect(),
49        )
50    }
51
52    #[cfg(feature = "package-reading")]
53    pub(crate) fn from_typst_entries(
54        entries: Vec<(String, Bytes)>,
55    ) -> Result<Self, PackageTreeError> {
56        Self::from_shared_entries(
57            entries
58                .into_iter()
59                .map(|(path, data)| (path, SharedBytes::from_typst(data)))
60                .collect(),
61        )
62    }
63
64    fn from_shared_entries(entries: Vec<(String, SharedBytes)>) -> Result<Self, PackageTreeError> {
65        let canonical_paths =
66            preflight_package_tree_paths(entries.iter().map(|(path, _)| path), |_| true).map_err(
67                |error| match error {
68                    PackageTreePathPreflightError::Invalid(source) => source,
69                    PackageTreePathPreflightError::RetentionLimit => {
70                        unreachable!("unlimited Package Tree construction preflight cannot exhaust")
71                    }
72                },
73            )?;
74        let canonical_entries = canonical_paths
75            .into_iter()
76            .zip(entries.into_iter().map(|(_, data)| data))
77            .collect::<Vec<_>>();
78
79        let files = canonical_entries.into_iter().collect::<BTreeMap<_, _>>();
80        let (identity, file_count, byte_length) =
81            derive_package_tree_identity(files.iter().map(|(path, data)| (path.as_str(), data)));
82        Ok(Self {
83            files,
84            identity,
85            file_count,
86            byte_length,
87        })
88    }
89
90    /// Constructs a tree by copying every file from caller-owned bytes.
91    pub fn copy_from_entries(
92        entries: impl IntoIterator<Item = (impl AsRef<str>, impl AsRef<[u8]>)>,
93    ) -> Result<Self, PackageTreeError> {
94        Self::from_owned_entries(
95            entries
96                .into_iter()
97                .map(|(path, data)| (path.as_ref().to_owned(), data.as_ref().to_vec())),
98        )
99    }
100
101    /// The files in canonical package-relative path order.
102    pub fn files(&self) -> impl Iterator<Item = (&str, &[u8])> {
103        self.files
104            .iter()
105            .map(|(path, data)| (path.as_str(), data.as_slice()))
106    }
107
108    /// Looks up a file by canonical package-relative path.
109    pub fn file(&self, path: &str) -> Option<&[u8]> {
110        self.files.get(path).map(SharedBytes::as_slice)
111    }
112
113    /// The Canonical Identity derived from every path and exact byte value.
114    pub fn identity(&self) -> CanonicalIdentity {
115        self.identity
116    }
117
118    /// The number of files in the tree.
119    pub fn file_count(&self) -> u64 {
120        self.file_count
121    }
122
123    /// The total exact byte length of every file in the tree.
124    pub fn byte_length(&self) -> u64 {
125        self.byte_length
126    }
127
128    pub(crate) fn shared_files(&self) -> impl Iterator<Item = (&str, &SharedBytes)> {
129        self.files.iter().map(|(path, data)| (path.as_str(), data))
130    }
131
132    pub(crate) fn shared_file(&self, path: &str) -> Option<&SharedBytes> {
133        self.files.get(path)
134    }
135
136    pub(crate) fn into_shared_files(self) -> BTreeMap<String, SharedBytes> {
137        self.files
138    }
139}
140
141pub(crate) fn derive_package_tree_identity<'a>(
142    files: impl IntoIterator<Item = (&'a str, &'a SharedBytes)>,
143) -> (CanonicalIdentity, u64, u64) {
144    let projection = files
145        .into_iter()
146        .map(|(path, data)| (path, data.len() as u64, typst::utils::hash128(data)))
147        .collect::<Vec<_>>();
148    let file_count = projection.len() as u64;
149    let byte_length = projection.iter().map(|(_, length, _)| length).sum();
150    (
151        CanonicalIdentity::from_digest(
152            CanonicalIdentityRole::PackageTree,
153            typst::utils::hash128(&(
154                "typst-pack-complete-package-tree-v1",
155                file_count,
156                byte_length,
157                projection,
158            )),
159        ),
160        file_count,
161        byte_length,
162    )
163}
164
165/// One independently detectable issue in a supplied Package Tree.
166#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
167#[non_exhaustive]
168pub enum PackageTreeIssue {
169    /// A supplied path cannot name a package-relative file.
170    #[error("package path {path:?} cannot be represented: {message:?}")]
171    InvalidPath { path: String, message: String },
172    /// Two supplied entries name one canonical package file.
173    #[error("package path {path:?} is supplied more than once")]
174    DuplicatePath { path: String },
175    /// One package file path is an ancestor of another package file path.
176    #[error("package path {ancestor:?} is a file ancestor of {descendant:?}")]
177    PathTreeConflict {
178        ancestor: String,
179        descendant: String,
180    },
181}
182
183impl PackageTreeIssue {
184    fn sort_key(&self) -> (&str, u8, &str) {
185        match self {
186            Self::InvalidPath { path, .. } => (path, 0, ""),
187            Self::DuplicatePath { path } => (path, 1, ""),
188            Self::PathTreeConflict {
189                ancestor,
190                descendant,
191            } => (ancestor, 2, descendant),
192        }
193    }
194}
195
196/// A failure while constructing a [`PackageTree`].
197#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
198#[error("package tree construction failed with {} issue(s)", .issues.len())]
199pub struct PackageTreeError {
200    issues: Vec<PackageTreeIssue>,
201}
202
203impl PackageTreeError {
204    /// Every independently detectable issue in canonical path and kind order.
205    pub fn issues(&self) -> &[PackageTreeIssue] {
206        &self.issues
207    }
208}
209
210pub(crate) enum PackageTreePathPreflightError {
211    Invalid(PackageTreeError),
212    RetentionLimit,
213}
214
215impl PackageTreePathPreflightError {
216    #[cfg(test)]
217    fn issues(&self) -> &[PackageTreeIssue] {
218        match self {
219            Self::Invalid(source) => source.issues(),
220            Self::RetentionLimit => &[],
221        }
222    }
223
224    #[cfg(test)]
225    fn is_retention_limit(&self) -> bool {
226        matches!(self, Self::RetentionLimit)
227    }
228}
229
230/// Validates Package Tree paths before payloads are read.
231///
232/// `retain` is called with the byte lengths of every path copy that would be
233/// kept by the plan or its error evidence. Returning `false` stops before those
234/// copies are retained.
235pub(crate) fn preflight_package_tree_paths(
236    paths: impl IntoIterator<Item = impl AsRef<str>>,
237    mut retain: impl FnMut(&[usize]) -> bool,
238) -> Result<Vec<String>, PackageTreePathPreflightError> {
239    let mut canonical_paths = Vec::new();
240    let mut issues = Vec::new();
241    for path in paths {
242        let path = path.as_ref();
243        match canonical_relative_path(path) {
244            Ok(canonical) => {
245                if !retain(&[canonical.as_str().len()]) {
246                    return Err(PackageTreePathPreflightError::RetentionLimit);
247                }
248                canonical_paths.push(canonical);
249            }
250            Err(message) => {
251                if !retain(&[path.len()]) {
252                    return Err(PackageTreePathPreflightError::RetentionLimit);
253                }
254                issues.push(PackageTreeIssue::InvalidPath {
255                    path: path.to_owned(),
256                    message: message.to_string(),
257                });
258            }
259        }
260    }
261
262    let mut ordered = canonical_paths
263        .iter()
264        .map(|path| path.as_str())
265        .collect::<Vec<_>>();
266    ordered.sort_unstable();
267    let mut last_duplicate = None;
268    for path in ordered
269        .windows(2)
270        .filter(|pair| pair[0] == pair[1])
271        .map(|pair| pair[0])
272    {
273        if last_duplicate == Some(path) {
274            continue;
275        }
276        last_duplicate = Some(path);
277        if !retain(&[path.len()]) {
278            return Err(PackageTreePathPreflightError::RetentionLimit);
279        }
280        issues.push(PackageTreeIssue::DuplicatePath {
281            path: path.to_owned(),
282        });
283    }
284
285    ordered.dedup();
286    for ancestor in &ordered {
287        if !retain(&[ancestor.len() + 1]) {
288            return Err(PackageTreePathPreflightError::RetentionLimit);
289        }
290    }
291    let conflicts = path_tree_conflicts(ordered.iter().map(|path| {
292        let canonical = canonical_paths
293            .iter()
294            .find(|canonical| canonical.as_str() == *path)
295            .expect("an ordered canonical path came from the preflight input");
296        (canonical, ())
297    }));
298    for conflict in conflicts {
299        if !retain(&[
300            conflict.ancestor.as_str().len(),
301            conflict.descendant.as_str().len(),
302        ]) {
303            return Err(PackageTreePathPreflightError::RetentionLimit);
304        }
305        issues.push(PackageTreeIssue::PathTreeConflict {
306            ancestor: conflict.ancestor.to_string(),
307            descendant: conflict.descendant.to_string(),
308        });
309    }
310
311    if issues.is_empty() {
312        Ok(canonical_paths
313            .into_iter()
314            .map(|path| path.into_string())
315            .collect())
316    } else {
317        issues.sort_by(|left, right| left.sort_key().cmp(&right.sort_key()));
318        Err(PackageTreePathPreflightError::Invalid(PackageTreeError {
319            issues,
320        }))
321    }
322}
323
324#[cfg(test)]
325mod path_preflight_tests {
326    use super::{PackageTreeIssue, preflight_package_tree_paths};
327
328    #[test]
329    fn path_preflight_is_the_authority_for_canonical_package_tree_shape() {
330        let paths = [
331            "dir/second.typ",
332            "same.typ",
333            "../escape.typ",
334            "./same.typ",
335            "dir",
336        ];
337        let error = preflight_package_tree_paths(paths, |_| true).unwrap_err();
338
339        assert_eq!(error.issues().len(), 3);
340        assert!(matches!(
341            &error.issues()[0],
342            PackageTreeIssue::InvalidPath { path, .. } if path == "../escape.typ"
343        ));
344        assert_eq!(
345            &error.issues()[1..],
346            &[
347                PackageTreeIssue::PathTreeConflict {
348                    ancestor: "dir".to_owned(),
349                    descendant: "dir/second.typ".to_owned(),
350                },
351                PackageTreeIssue::DuplicatePath {
352                    path: "same.typ".to_owned(),
353                },
354            ]
355        );
356    }
357
358    #[test]
359    fn path_preflight_stops_before_retaining_unbudgeted_evidence() {
360        let mut retained = 0usize;
361        let error = preflight_package_tree_paths(["dir", "dir/file.typ"], |lengths| {
362            let requested = lengths.iter().sum::<usize>();
363            if retained + requested > 20 {
364                return false;
365            }
366            retained += requested;
367            true
368        })
369        .unwrap_err();
370
371        assert!(error.is_retention_limit());
372        assert_eq!(retained, 19);
373    }
374}
375
376/// One Package Catalog entry under its claimed exact specification.
377#[derive(Clone, Debug, PartialEq, Eq)]
378pub struct PackageCatalogEntry {
379    spec: PackageSpec,
380    tree: PackageTree,
381    disposition: PackageDisposition,
382}
383
384impl PackageCatalogEntry {
385    /// The exact specification this entry claims to satisfy.
386    pub fn spec(&self) -> &PackageSpec {
387        &self.spec
388    }
389
390    /// The validated Package Tree.
391    pub fn tree(&self) -> &PackageTree {
392        &self.tree
393    }
394
395    /// Whether this tree is embedded or externally fulfilled.
396    pub fn disposition(&self) -> PackageDisposition {
397        self.disposition
398    }
399}
400
401/// The validated Package Trees Pack Creation may select, keyed canonically by
402/// exact package specification.
403#[derive(Clone, Debug, Default, PartialEq, Eq)]
404pub struct PackageCatalog {
405    entries: BTreeMap<String, PackageCatalogEntry>,
406}
407
408impl PackageCatalog {
409    /// An empty catalog.
410    pub fn new() -> Self {
411        Self::default()
412    }
413
414    /// Constructs a catalog from claimed specifications, trees, and explicit
415    /// dispositions.
416    pub fn from_entries(
417        entries: impl IntoIterator<Item = (PackageSpec, PackageTree, PackageDisposition)>,
418    ) -> Result<Self, PackageCatalogError> {
419        let entries = entries.into_iter().collect::<Vec<_>>();
420        let mut seen = BTreeSet::new();
421        let mut duplicates = BTreeSet::new();
422        let mut issues = Vec::new();
423        for (spec, tree, _) in &entries {
424            let key = spec.to_string();
425            if !seen.insert(key.clone()) {
426                duplicates.insert(key);
427            }
428            issues.extend(verify_package_declaration(spec, tree));
429        }
430        for key in duplicates {
431            let spec = entries
432                .iter()
433                .find(|(spec, _, _)| spec.to_string() == key)
434                .expect("duplicate specification came from an entry")
435                .0
436                .clone();
437            issues.push(PackageCatalogIssue::DuplicateSpecification { spec });
438        }
439        issues.sort_by_key(PackageCatalogIssue::sort_key);
440        if !issues.is_empty() {
441            return Err(PackageCatalogError { issues });
442        }
443        Ok(Self {
444            entries: entries
445                .into_iter()
446                .map(|(spec, tree, disposition)| {
447                    (
448                        spec.to_string(),
449                        PackageCatalogEntry {
450                            spec,
451                            tree,
452                            disposition,
453                        },
454                    )
455                })
456                .collect(),
457        })
458    }
459
460    /// Inserts one validated tree, rejecting an existing exact specification
461    /// rather than replacing its evidence.
462    pub fn insert(
463        &mut self,
464        spec: PackageSpec,
465        tree: PackageTree,
466        disposition: PackageDisposition,
467    ) -> Result<(), PackageCatalogError> {
468        let key = spec.to_string();
469        let mut issues = Vec::new();
470        if self.entries.contains_key(&key) {
471            issues.push(PackageCatalogIssue::DuplicateSpecification { spec: spec.clone() });
472        }
473        issues.extend(verify_package_declaration(&spec, &tree));
474        issues.sort_by_key(PackageCatalogIssue::sort_key);
475        if !issues.is_empty() {
476            return Err(PackageCatalogError { issues });
477        }
478        self.entries.insert(
479            key,
480            PackageCatalogEntry {
481                spec,
482                tree,
483                disposition,
484            },
485        );
486        Ok(())
487    }
488
489    /// Catalog entries in canonical exact-specification order.
490    pub fn entries(&self) -> impl Iterator<Item = &PackageCatalogEntry> {
491        self.entries.values()
492    }
493
494    /// Looks up one exact package specification.
495    pub fn get(&self, spec: &PackageSpec) -> Option<&PackageCatalogEntry> {
496        self.entries.get(&spec.to_string())
497    }
498}
499
500const PACKAGE_DECLARATION_PATH: &str = "typst.toml";
501
502fn verify_package_declaration(spec: &PackageSpec, tree: &PackageTree) -> Vec<PackageCatalogIssue> {
503    let Some(data) = tree.file(PACKAGE_DECLARATION_PATH) else {
504        return vec![PackageCatalogIssue::MissingDeclaration { spec: spec.clone() }];
505    };
506    let Ok(text) = std::str::from_utf8(data) else {
507        return vec![PackageCatalogIssue::DeclarationNotUtf8 { spec: spec.clone() }];
508    };
509    let declaration = match toml::from_str::<SuppliedPackageDeclaration>(text) {
510        Ok(declaration) => declaration,
511        Err(error) => {
512            return vec![PackageCatalogIssue::MalformedDeclaration {
513                spec: spec.clone(),
514                message: error.message().to_owned(),
515            }];
516        }
517    };
518
519    let mut issues = Vec::new();
520    if declaration.package.name != spec.name.as_str() {
521        issues.push(PackageCatalogIssue::MismatchedName {
522            spec: spec.clone(),
523            declared: declaration.package.name,
524        });
525    }
526    if declaration.package.version != spec.version {
527        issues.push(PackageCatalogIssue::MismatchedVersion {
528            spec: spec.clone(),
529            declared: declaration.package.version,
530        });
531    }
532    issues
533}
534
535#[derive(serde::Deserialize)]
536struct SuppliedPackageDeclaration {
537    package: DeclaredPackage,
538}
539
540#[derive(serde::Deserialize)]
541struct DeclaredPackage {
542    name: String,
543    version: PackageVersion,
544}
545
546/// One independently detectable issue in a supplied Package Catalog.
547#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
548#[non_exhaustive]
549pub enum PackageCatalogIssue {
550    /// An exact package specification was supplied more than once.
551    #[error("package specification {spec} is supplied more than once")]
552    DuplicateSpecification { spec: PackageSpec },
553    /// The tree has no `typst.toml` declaration.
554    #[error("the tree supplied for package {spec} holds no `typst.toml`")]
555    MissingDeclaration { spec: PackageSpec },
556    /// The tree's `typst.toml` is not UTF-8.
557    #[error("the tree supplied for package {spec} has a non-UTF-8 `typst.toml`")]
558    DeclarationNotUtf8 { spec: PackageSpec },
559    /// The tree's `typst.toml` cannot be parsed.
560    #[error("the tree supplied for package {spec} has malformed `typst.toml`: {message:?}")]
561    MalformedDeclaration { spec: PackageSpec, message: String },
562    /// The declaration names another package.
563    #[error("the tree supplied for package {spec} declares the name {declared:?}")]
564    MismatchedName { spec: PackageSpec, declared: String },
565    /// The declaration names another package version.
566    #[error("the tree supplied for package {spec} declares the version {declared}")]
567    MismatchedVersion {
568        spec: PackageSpec,
569        declared: PackageVersion,
570    },
571}
572
573impl PackageCatalogIssue {
574    fn spec(&self) -> &PackageSpec {
575        match self {
576            Self::DuplicateSpecification { spec }
577            | Self::MissingDeclaration { spec }
578            | Self::DeclarationNotUtf8 { spec }
579            | Self::MalformedDeclaration { spec, .. }
580            | Self::MismatchedName { spec, .. }
581            | Self::MismatchedVersion { spec, .. } => spec,
582        }
583    }
584
585    fn sort_key(&self) -> (String, u8, String) {
586        let (rank, detail) = match self {
587            Self::DuplicateSpecification { .. } => (0, String::new()),
588            Self::MissingDeclaration { .. } => (1, String::new()),
589            Self::DeclarationNotUtf8 { .. } => (2, String::new()),
590            Self::MalformedDeclaration { message, .. } => (3, message.clone()),
591            Self::MismatchedName { declared, .. } => (4, declared.clone()),
592            Self::MismatchedVersion { declared, .. } => (5, declared.to_string()),
593        };
594        (self.spec().to_string(), rank, detail)
595    }
596}
597
598/// A failure while constructing a [`PackageCatalog`].
599#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
600#[error("package catalog construction failed with {} issue(s)", .issues.len())]
601pub struct PackageCatalogError {
602    issues: Vec<PackageCatalogIssue>,
603}
604
605impl PackageCatalogError {
606    /// Every independently detectable issue in canonical specification and
607    /// issue-kind order.
608    pub fn issues(&self) -> &[PackageCatalogIssue] {
609        &self.issues
610    }
611}
typst_pack/package_catalog.rs

typst_pack/
package_catalog.rs
