typst_html/
link.rs

1use std::collections::VecDeque;
2use std::sync::Arc;
3
4use ecow::{EcoString, EcoVec, eco_vec};
5use rustc_hash::{FxHashMap, FxHashSet};
6use typst_library::foundations::Label;
7use typst_library::introspection::{DocumentPosition, InnerHtmlPosition, Location, Tag};
8use typst_library::layout::{Frame, FrameItem, Point};
9use typst_library::model::AnchorGenerator;
10
11use crate::{HtmlDocument, HtmlElement, HtmlNode, attr, tag};
12
13/// Attaches IDs to nodes produced by link targets to make them linkable.
14///
15/// The `targets` set should contain the locations of all elements in the HTML
16/// document that are linked to from somewhere.
17///
18/// May produce `<span>`s for link targets that turned into text nodes or no
19/// nodes at all. See the [`LinkElem`](typst_library::model::LinkElem)
20/// documentation for more details.
21///
22/// Anchor ID generation attempts to use existing HTML element IDs and Typst
23/// labels to generate human-readable fragment names. If a label occurs multiple
24/// times, it's disambiguated with a suffix. This disambiguation is per
25/// document, even in bundle output. It uses the document's own introspector.
26pub fn create_link_anchors(
27    document: &mut HtmlDocument,
28    targets: &FxHashSet<Location>,
29) -> FxHashMap<Location, EcoString> {
30    if targets.is_empty() {
31        // Nothing to do.
32        return FxHashMap::default();
33    }
34
35    // Assign IDs to all link targets.
36    let mut work = Work::new();
37    let introspector = Arc::clone(document.introspector());
38    traverse(
39        &mut work,
40        targets,
41        &mut AnchorGenerator::new(introspector.as_ref()),
42        &mut document.root_mut().children,
43    );
44    work.ids
45}
46
47/// Traverses a list of nodes.
48fn traverse(
49    work: &mut Work,
50    targets: &FxHashSet<Location>,
51    generator: &mut AnchorGenerator<'_>,
52    nodes: &mut EcoVec<HtmlNode>,
53) {
54    let mut i = 0;
55    while i < nodes.len() {
56        let node = &mut nodes.make_mut()[i];
57        match node {
58            // When visiting a start tag, we check whether the element needs an
59            // ID and if so, add it to the queue, so that its first child node
60            // receives an ID.
61            HtmlNode::Tag(Tag::Start(elem, _)) => {
62                let loc = elem.location().unwrap();
63                if targets.contains(&loc) {
64                    work.enqueue(loc, elem.label());
65                }
66            }
67
68            // When we reach an end tag, we check whether it closes an element
69            // that is still in our queue. If so, that means the element
70            // produced no nodes and we need to insert an empty span.
71            HtmlNode::Tag(Tag::End(loc, _, _)) => {
72                work.remove(*loc, |label| {
73                    let mut element = HtmlElement::new(tag::span);
74                    let id = generator.assign(&mut element, label);
75                    nodes.insert(i + 1, HtmlNode::Element(element));
76                    id
77                });
78            }
79
80            // When visiting an element and the queue is non-empty, we assign an
81            // ID. Then, we traverse its children.
82            HtmlNode::Element(element) => {
83                work.drain(|label| generator.assign(element, label));
84                traverse(work, targets, generator, &mut element.children);
85            }
86
87            // When visiting text and the queue is non-empty, we generate a span
88            // and assign an ID.
89            HtmlNode::Text(..) => {
90                work.drain(|label| {
91                    let mut element =
92                        HtmlElement::new(tag::span).with_children(eco_vec![node.clone()]);
93                    let id = generator.assign(&mut element, label);
94                    *node = HtmlNode::Element(element);
95                    id
96                });
97            }
98
99            // When visiting a frame and the queue is non-empty, we assign an
100            // ID to it (will be added to the resulting SVG element).
101            HtmlNode::Frame(frame) => {
102                work.drain(|label| {
103                    frame.id.get_or_insert_with(|| generator.identify(label)).clone()
104                });
105                traverse_frame(
106                    work,
107                    targets,
108                    generator,
109                    &frame.inner,
110                    &mut frame.anchors,
111                );
112            }
113        }
114
115        i += 1;
116    }
117}
118
119/// Traverses a frame embedded in HTML.
120fn traverse_frame(
121    work: &mut Work,
122    targets: &FxHashSet<Location>,
123    generator: &mut AnchorGenerator<'_>,
124    frame: &Frame,
125    anchors: &mut EcoVec<(Point, EcoString)>,
126) {
127    for (_, item) in frame.items() {
128        match item {
129            FrameItem::Tag(Tag::Start(elem, _)) => {
130                let loc = elem.location().unwrap();
131                if targets.contains(&loc)
132                    && let Some(DocumentPosition::Html(position)) =
133                        generator.introspector().position(loc)
134                    && let Some(InnerHtmlPosition::Frame(point)) = position.details()
135                {
136                    let id = generator.identify(elem.label());
137                    work.ids.insert(loc, id.clone());
138                    anchors.push((*point, id));
139                }
140            }
141            FrameItem::Group(group) => {
142                traverse_frame(work, targets, generator, &group.frame, anchors);
143            }
144            _ => {}
145        }
146    }
147}
148
149/// Keeps track of the work to be done during ID generation.
150struct Work {
151    /// The locations and labels of elements we need to assign an ID to right
152    /// now.
153    queue: VecDeque<(Location, Option<Label>)>,
154    /// The resulting mapping from element location's to HTML IDs.
155    ids: FxHashMap<Location, EcoString>,
156}
157
158impl Work {
159    /// Sets up.
160    fn new() -> Self {
161        Self { queue: VecDeque::new(), ids: FxHashMap::default() }
162    }
163
164    /// Marks the element with the given location and label as in need of an
165    /// ID. A subsequent call to `drain` will call `f`.
166    fn enqueue(&mut self, loc: Location, label: Option<Label>) {
167        self.queue.push_back((loc, label))
168    }
169
170    /// If one or multiple elements are in need of an ID, calls `f` to generate
171    /// an ID and apply it to the current node with `f`, and then establishes a
172    /// mapping from the elements' locations to that ID.
173    fn drain(&mut self, f: impl FnOnce(Option<Label>) -> EcoString) {
174        if let Some(&(_, label)) = self.queue.front() {
175            let id = f(label);
176            for (loc, _) in self.queue.drain(..) {
177                self.ids.insert(loc, id.clone());
178            }
179        }
180    }
181
182    /// Similar to `drain`, but only for a specific given location.
183    fn remove(&mut self, loc: Location, f: impl FnOnce(Option<Label>) -> EcoString) {
184        if let Some(i) = self.queue.iter().position(|&(l, _)| l == loc) {
185            let (_, label) = self.queue.remove(i).unwrap();
186            let id = f(label);
187            self.ids.insert(loc, id.clone());
188        }
189    }
190}
191
192trait AnchorGeneratorExt {
193    /// Assigns an ID to an element or reuses an existing ID.
194    fn assign(&mut self, element: &mut HtmlElement, label: Option<Label>) -> EcoString;
195}
196
197impl AnchorGeneratorExt for AnchorGenerator<'_> {
198    fn assign(&mut self, element: &mut HtmlElement, label: Option<Label>) -> EcoString {
199        element.attrs.get(attr::id).cloned().unwrap_or_else(|| {
200            let id = self.identify(label);
201            element.attrs.push_front(attr::id, id.clone());
202            id
203        })
204    }
205}
typst_html/link.rs

typst_html/
link.rs
