Fix named destinations (#3411)

5 files changed, 74 insertions, 59 deletions

diff --git a/Cargo.lock b/Cargo.lock
index d3ddcf6e..13a11278 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1616,8 +1616,9 @@ checksum = "8835116a5c179084a830efb3adc117ab007512b535bc1a21c991d3b32a6b44dd"
 
 [[package]]
 name = "pdf-writer"
-version = "0.9.0"
-source = "git+https://github.com/heinenen/pdf-writer?branch=named_destinations#58c6dc1552aa72f5e2c07a37045526fcf365d34a"
+version = "0.9.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "644b654f2de28457bf1e25a4905a76a563d1128a33ce60cf042f721f6818feaf"
 dependencies = [
  "bitflags 1.3.2",
  "itoa",
diff --git a/Cargo.toml b/Cargo.toml
index 9da3f904..6333cbb0 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -71,7 +71,7 @@ oxipng = { version = "9.0", default-features = false, features = ["filetime", "p
 palette = { version = "0.7.3", default-features = false, features = ["approx", "libm"] }
 parking_lot = "0.12.1"
 pathdiff = "0.2"
-pdf-writer = "0.9"
+pdf-writer = "0.9.2"
 phf = { version = "0.11", features = ["macros"] }
 pixglyph = "0.3"
 proc-macro2 = "1"
@@ -123,9 +123,6 @@ xz2 = "0.1"
 yaml-front-matter = "0.1"
 zip = { version = "0.6", default-features = false, features = ["deflate"] }
 
-[patch.crates-io]
-pdf-writer = { git = 'https://github.com/heinenen/pdf-writer', branch = "named_destinations" }
-
 [profile.dev.package."*"]
 opt-level = 2
 
diff --git a/crates/typst-pdf/src/lib.rs b/crates/typst-pdf/src/lib.rs
index 9cf345a7..467b4ffb 100644
--- a/crates/typst-pdf/src/lib.rs
+++ b/crates/typst-pdf/src/lib.rs
@@ -17,8 +17,10 @@ use std::sync::Arc;
 use base64::Engine;
 use ecow::{eco_format, EcoString};
 use pdf_writer::types::Direction;
+use pdf_writer::writers::Destination;
 use pdf_writer::{Finish, Name, Pdf, Ref, Str, TextStr};
-use typst::foundations::{Datetime, NativeElement};
+use typst::foundations::{Datetime, Label, NativeElement};
+use typst::introspection::Location;
 use typst::layout::{Abs, Dir, Em, Transform};
 use typst::model::{Document, HeadingElem};
 use typst::text::{Font, Lang};
@@ -60,6 +62,7 @@ pub fn pdf(
     gradient::write_gradients(&mut ctx);
     extg::write_external_graphics_states(&mut ctx);
     pattern::write_patterns(&mut ctx);
+    write_named_destinations(&mut ctx);
     page::write_page_tree(&mut ctx);
     write_catalog(&mut ctx, ident, timestamp);
     ctx.pdf.finish()
@@ -115,6 +118,11 @@ struct PdfContext<'a> {
     pattern_map: Remapper<PdfPattern>,
     /// Deduplicates external graphics states used across the document.
     extg_map: Remapper<ExtGState>,
+
+    /// A sorted list of all named destinations.
+    dests: Vec<(Label, Ref)>,
+    /// Maps from locations to named destinations that point to them.
+    loc_to_dest: HashMap<Location, Label>,
 }
 
 impl<'a> PdfContext<'a> {
@@ -142,6 +150,8 @@ impl<'a> PdfContext<'a> {
             gradient_map: Remapper::new(),
             pattern_map: Remapper::new(),
             extg_map: Remapper::new(),
+            dests: vec![],
+            loc_to_dest: HashMap::new(),
         }
     }
 }
@@ -252,20 +262,18 @@ fn write_catalog(ctx: &mut PdfContext, ident: Option<&str>, timestamp: Option<Da
         .pair(Name(b"Type"), Name(b"Metadata"))
         .pair(Name(b"Subtype"), Name(b"XML"));
 
-    let destinations = write_and_collect_destinations(ctx);
-
     // Write the document catalog.
     let mut catalog = ctx.pdf.catalog(ctx.alloc.bump());
     catalog.pages(ctx.page_tree_ref);
     catalog.viewer_preferences().direction(dir);
     catalog.metadata(meta_ref);
 
-    // Write the named destinations.
+    // Write the named destination tree.
     let mut name_dict = catalog.names();
     let mut dests_name_tree = name_dict.destinations();
     let mut names = dests_name_tree.names();
-    for (name, dest_ref, _page_ref, _x, _y) in destinations {
-        names.insert(name, dest_ref);
+    for &(name, dest_ref, ..) in &ctx.dests {
+        names.insert(Str(name.as_str().as_bytes()), dest_ref);
     }
     names.finish();
     dests_name_tree.finish();
@@ -291,38 +299,43 @@ fn write_catalog(ctx: &mut PdfContext, ident: Option<&str>, timestamp: Option<Da
     catalog.finish();
 }
 
-fn write_and_collect_destinations<'a>(
-    ctx: &mut PdfContext,
-) -> Vec<(Str<'a>, Ref, Ref, f32, f32)> {
-    let mut destinations = vec![];
-
-    let mut seen_labels = HashSet::new();
-    let elements = ctx.document.introspector.query(&HeadingElem::elem().select());
-    for elem in elements.iter() {
-        let heading = elem.to_packed::<HeadingElem>().unwrap();
-        if let Some(label) = heading.label() {
-            if !seen_labels.contains(&label) {
-                let loc = heading.location().unwrap();
-                let name = Str(label.as_str().as_bytes());
-                let pos = ctx.document.introspector.position(loc);
-                let index = pos.page.get() - 1;
-                let y = (pos.point.y - Abs::pt(10.0)).max(Abs::zero());
-                if let Some(page) = ctx.pages.get(index) {
-                    seen_labels.insert(label);
-                    let page_ref = ctx.page_refs[index];
-                    let x = pos.point.x.to_f32();
-                    let y = (page.size.y - y).to_f32();
-                    let dest_ref = ctx.alloc.bump();
-                    destinations.push((name, dest_ref, page_ref, x, y))
-                }
-            }
+/// Fills in the map and vector for named destinations and writes the indirect
+/// destination objects.
+fn write_named_destinations(ctx: &mut PdfContext) {
+    let mut seen = HashSet::new();
+
+    // Find all headings that have a label and are the first among other
+    // headings with the same label.
+    let mut matches: Vec<_> = ctx
+        .document
+        .introspector
+        .query(&HeadingElem::elem().select())
+        .iter()
+        .filter_map(|elem| elem.location().zip(elem.label()))
+        .filter(|&(_, label)| seen.insert(label))
+        .collect();
+
+    // Named destinations must be sorted by key.
+    matches.sort_by_key(|&(_, label)| label);
+
+    for (loc, label) in matches {
+        let pos = ctx.document.introspector.position(loc);
+        let index = pos.page.get() - 1;
+        let y = (pos.point.y - Abs::pt(10.0)).max(Abs::zero());
+
+        if let Some(page) = ctx.pages.get(index) {
+            let dest_ref = ctx.alloc.bump();
+            let x = pos.point.x.to_f32();
+            let y = (page.size.y - y).to_f32();
+            ctx.dests.push((label, dest_ref));
+            ctx.loc_to_dest.insert(loc, label);
+            ctx.pdf
+                .indirect(dest_ref)
+                .start::<Destination>()
+                .page(page.id)
+                .xyz(x, y, None);
         }
     }
-    destinations.sort_by_key(|i| i.0);
-    for (_name, dest_ref, page_ref, x, y) in destinations.iter().copied() {
-        ctx.pdf.destination(dest_ref).page(page_ref).xyz(x, y, None);
-    }
-    destinations
 }
 
 /// Compress data with the DEFLATE algorithm.
diff --git a/crates/typst-pdf/src/page.rs b/crates/typst-pdf/src/page.rs
index b18c2878..ddcfe50f 100644
--- a/crates/typst-pdf/src/page.rs
+++ b/crates/typst-pdf/src/page.rs
@@ -8,12 +8,11 @@ use pdf_writer::types::{
 };
 use pdf_writer::writers::PageLabel;
 use pdf_writer::{Content, Filter, Finish, Name, Rect, Ref, Str, TextStr};
-use typst::foundations::{NativeElement, Selector};
-use typst::introspection::{Location, Meta};
+use typst::introspection::Meta;
 use typst::layout::{
     Abs, Em, Frame, FrameItem, GroupItem, Page, Point, Ratio, Size, Transform,
 };
-use typst::model::{Destination, Document, HeadingElem, Numbering};
+use typst::model::{Destination, Numbering};
 use typst::text::{Case, Font, TextItem};
 use typst::util::{Deferred, Numeric};
 use typst::visualize::{
@@ -142,16 +141,6 @@ pub(crate) fn write_page_tree(ctx: &mut PdfContext) {
     ctx.colors.write_functions(&mut ctx.pdf);
 }
 
-fn name_from_loc<'a>(doc: &Document, loc: &Location) -> Option<Name<'a>> {
-    let elem = doc.introspector.query_first(&Selector::Location(*loc))?;
-    let label = elem.label()?;
-    debug_assert!(doc.introspector.query_label(label).is_ok());
-    if elem.elem() != HeadingElem::elem() {
-        return None;
-    }
-    Some(Name(label.as_str().as_bytes()))
-}
-
 /// Write a page tree node.
 fn write_page(ctx: &mut PdfContext, i: usize) {
     let page = &ctx.pages[i];
@@ -191,11 +180,12 @@ fn write_page(ctx: &mut PdfContext, i: usize) {
             }
             Destination::Position(pos) => *pos,
             Destination::Location(loc) => {
-                if let Some(name) = name_from_loc(ctx.document, loc) {
+                if let Some(key) = ctx.loc_to_dest.get(loc) {
                     annotation
                         .action()
                         .action_type(ActionType::GoTo)
-                        .destination_named(name);
+                        // `key` must be a `Str`, not a `Name`.
+                        .pair(Name(b"D"), Str(key.as_str().as_bytes()));
                     continue;
                 } else {
                     ctx.document.introspector.position(*loc)
@@ -205,12 +195,13 @@ fn write_page(ctx: &mut PdfContext, i: usize) {
 
         let index = pos.page.get() - 1;
         let y = (pos.point.y - Abs::pt(10.0)).max(Abs::zero());
+
         if let Some(page) = ctx.pages.get(index) {
             annotation
                 .action()
                 .action_type(ActionType::GoTo)
                 .destination()
-                .page(ctx.page_refs[index])
+                .page(page.id)
                 .xyz(pos.point.x.to_f32(), (page.size.y - y).to_f32(), None);
         }
     }
diff --git a/crates/typst/src/util/pico.rs b/crates/typst/src/util/pico.rs
index 827d6b5b..60af23ee 100644
--- a/crates/typst/src/util/pico.rs
+++ b/crates/typst/src/util/pico.rs
@@ -1,3 +1,4 @@
+use std::cmp::Ordering;
 use std::collections::HashMap;
 use std::fmt::{self, Debug, Formatter};
 use std::sync::RwLock;
@@ -23,7 +24,7 @@ struct Interner {
 /// slow to look up a string in the interner, so we want to avoid doing it
 /// unnecessarily. For this reason, the user should use the [`PicoStr::resolve`]
 /// method to get the underlying string, such that the lookup is done only once.
-#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
 pub struct PicoStr(u32);
 
 impl PicoStr {
@@ -63,6 +64,18 @@ impl Debug for PicoStr {
     }
 }
 
+impl Ord for PicoStr {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.resolve().cmp(other.resolve())
+    }
+}
+
+impl PartialOrd for PicoStr {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl AsRef<str> for PicoStr {
     fn as_ref(&self) -> &str {
         self.resolve()