sphinx_ultra/doctree/
ids.rs

1//! docutils-exact id/name normalization and the document id registry.
2//!
3//! Algorithms ported from docutils 0.22.4 `nodes.py` (`make_id`,
4//! `fully_normalize_name`, `whitespace_normalize_name`, `document.set_id`,
5//! `set_name_id_map`/`set_duplicate_name_id`), with the Sphinx settings
6//! `id_prefix=''`, `auto_id_prefix='id'` baked in (sphinx/environment
7//! overrides docutils' `'%'` default — auto ids are `id1`, `id2`, …).
8
9use std::collections::{HashMap, HashSet};
10
11use unicode_normalization::UnicodeNormalization;
12
13use super::messages;
14use super::Node;
15
16/// docutils `_non_id_translate_digraphs` (applied after lowercasing).
17fn translate_digraph(c: char) -> Option<&'static str> {
18    Some(match c as u32 {
19        223 => "sz", // ß
20        230 => "ae", // æ
21        339 => "oe", // œ
22        568 => "db", // ȸ
23        569 => "qp", // ȹ
24        _ => return None,
25    })
26}
27
28/// docutils `_non_id_translate` (single-char replacements).
29fn translate_single(c: char) -> Option<char> {
30    Some(match c as u32 {
31        248 => 'o', // ø
32        273 => 'd', // đ
33        295 => 'h', // ħ
34        305 => 'i', // ı
35        322 => 'l', // ł
36        359 => 't', // ŧ
37        384 => 'b', // ƀ
38        387 => 'b', // ƃ
39        392 => 'c', // ƈ
40        396 => 'd', // ƌ
41        402 => 'f', // ƒ
42        409 => 'k', // ƙ
43        410 => 'l', // ƚ
44        414 => 'n', // ƞ
45        421 => 'p', // ƥ
46        427 => 't', // ƫ
47        429 => 't', // ƭ
48        436 => 'y', // ƴ
49        438 => 'z', // ƶ
50        485 => 'g', // ǥ
51        549 => 'z', // ȥ
52        564 => 'l', // ȴ
53        565 => 'n', // ȵ
54        566 => 't', // ȶ
55        567 => 'j', // ȷ
56        572 => 'c', // ȼ
57        575 => 's', // ȿ
58        576 => 'z', // ɀ
59        583 => 'e', // ɇ
60        585 => 'j', // ɉ
61        587 => 'q', // ɋ
62        589 => 'r', // ɍ
63        591 => 'y', // ɏ
64        _ => return None,
65    })
66}
67
68/// docutils `nodes.make_id`. Result grammar: `[a-z](-?[a-z0-9]+)*` or empty.
69pub fn make_id(s: &str) -> String {
70    // 1. lowercase FIRST (order is load-bearing: Ü -> ü -> NFKD u).
71    let lowered = s.to_lowercase();
72    // 2. digraph + single-char translate tables (disjoint key sets).
73    let mut translated = String::with_capacity(lowered.len());
74    for c in lowered.chars() {
75        if let Some(d) = translate_digraph(c) {
76            translated.push_str(d);
77        } else if let Some(r) = translate_single(c) {
78            translated.push(r);
79        } else {
80            translated.push(c);
81        }
82    }
83    // 3. NFKD-normalize, drop remaining non-ASCII.
84    let ascii: String = translated.nfkd().filter(char::is_ascii).collect();
85    // 4. collapse whitespace runs (' '.join(s.split())).
86    let collapsed = ascii.split_whitespace().collect::<Vec<_>>().join(" ");
87    // 5. every [^a-z0-9]+ run -> single '-'.
88    let mut out = String::with_capacity(collapsed.len());
89    let mut in_run = false;
90    for c in collapsed.chars() {
91        if c.is_ascii_lowercase() || c.is_ascii_digit() {
92            out.push(c);
93            in_run = false;
94        } else if !in_run {
95            out.push('-');
96            in_run = true;
97        }
98    }
99    // 6. strip leading [-0-9]+ and trailing -+ (ASCII-only by now).
100    let bytes = out.as_bytes();
101    let mut start = 0;
102    while start < bytes.len() && (bytes[start] == b'-' || bytes[start].is_ascii_digit()) {
103        start += 1;
104    }
105    let mut end = bytes.len();
106    while end > start && bytes[end - 1] == b'-' {
107        end -= 1;
108    }
109    out[start..end].to_string()
110}
111
112/// docutils `fully_normalize_name`: lowercase + collapse whitespace.
113pub fn fully_normalize_name(s: &str) -> String {
114    s.to_lowercase()
115        .split_whitespace()
116        .collect::<Vec<_>>()
117        .join(" ")
118}
119
120/// docutils `whitespace_normalize_name`: collapse whitespace, keep case.
121pub fn whitespace_normalize_name(s: &str) -> String {
122    s.split_whitespace().collect::<Vec<_>>().join(" ")
123}
124
125/// A deferred "first node loses its name too" fixup: on a duplicate name,
126/// docutils dupnames BOTH nodes, but the first one is already deep in the
127/// tree — the parser applies these after parsing via
128/// [`apply_dupname_fixups`].
129#[derive(Debug, Clone, PartialEq, Eq)]
130pub struct DupnameFixup {
131    pub name: String,
132    pub node_id: String,
133}
134
135/// Document-level id/name registry (docutils `document.ids`/`nameids`/
136/// `id_counter` with Sphinx auto-id settings).
137#[derive(Debug, Clone)]
138struct NameEntry {
139    /// Some(id) while the name maps uniquely; None once duplicated away.
140    id: Option<String>,
141    explicit: bool,
142    refuri: Option<String>,
143}
144
145#[derive(Debug, Default)]
146pub struct IdRegistry {
147    ids: HashSet<String>,
148    nameids: HashMap<String, NameEntry>,
149    /// per-prefix auto-id counters (only "id" in wave 1).
150    id_counter: HashMap<&'static str, u64>,
151    fixups: Vec<DupnameFixup>,
152}
153
154impl IdRegistry {
155    pub fn new() -> Self {
156        Self::default()
157    }
158
159    /// docutils `document.set_id` (id_prefix='', auto_id_prefix='id'):
160    /// first unregistered nonempty `make_id(name)` wins; otherwise `idN`.
161    fn allocate_id(&mut self, names: &[String]) -> String {
162        for name in names {
163            let base = make_id(name);
164            if !base.is_empty() && !self.ids.contains(&base) {
165                self.ids.insert(base.clone());
166                return base;
167            }
168        }
169        loop {
170            let counter = self.id_counter.entry("id").or_insert(0);
171            *counter += 1;
172            let id = format!("id{counter}");
173            if !self.ids.contains(&id) {
174                self.ids.insert(id.clone());
175                return id;
176            }
177        }
178    }
179
180    fn dupname_new(node: &mut Node, name: &str) {
181        if let Some(pos) = node.attrs.names.iter().position(|n| n == name) {
182            node.attrs.names.remove(pos);
183            node.attrs.dupnames.push(name.to_string());
184        }
185    }
186
187    /// docutils `set_name_id_map`/`set_duplicate_name_id` with the
188    /// explicit-vs-implicit precedence table (fixture-verified):
189    /// - implicit vs implicit: BOTH dupname'd, INFO "Duplicate implicit …"
190    /// - explicit vs explicit: BOTH dupname'd, WARNING "Duplicate explicit …"
191    ///   (unless both share an identical refuri: new dupname'd silently)
192    /// - new implicit vs old explicit: only the NEW node dupname'd, INFO
193    /// - new explicit vs old implicit: OLD dupname'd, new KEEPS the name,
194    ///   INFO "Target name overrides implicit target name …"
195    fn register(
196        &mut self,
197        node: &mut Node,
198        line: u32,
199        source: &str,
200        explicit: bool,
201        backrefs_on_msg: bool,
202        refuri: Option<&str>,
203    ) -> Option<Node> {
204        let id = self.allocate_id(&node.attrs.names);
205        node.attrs.ids.push(id.clone());
206
207        let mut message = None;
208        let names = node.attrs.names.clone();
209        for name in names {
210            let Some(entry) = self.nameids.get(&name).cloned() else {
211                self.nameids.insert(
212                    name,
213                    NameEntry {
214                        id: Some(id.clone()),
215                        explicit,
216                        refuri: refuri.map(str::to_string),
217                    },
218                );
219                continue;
220            };
221            let dup_info = |level: u8, text: String, with_backrefs: bool| {
222                let mut msg = messages::system_message(level, &text, line, source);
223                if with_backrefs {
224                    msg.attrs.backrefs.push(id.clone());
225                }
226                msg
227            };
228            match (entry.explicit, explicit) {
229                (true, true) => {
230                    if refuri.is_some() && entry.refuri.as_deref() == refuri {
231                        // Identical external duplicate: silent, new dupname'd.
232                        Self::dupname_new(node, &name);
233                        continue;
234                    }
235                    if let Some(old_id) = entry.id.clone() {
236                        self.fixups.push(DupnameFixup {
237                            name: name.clone(),
238                            node_id: old_id,
239                        });
240                    }
241                    self.nameids.insert(
242                        name.clone(),
243                        NameEntry {
244                            id: None,
245                            explicit: true,
246                            refuri: None,
247                        },
248                    );
249                    Self::dupname_new(node, &name);
250                    message = Some(dup_info(
251                        messages::WARNING,
252                        format!("Duplicate explicit target name: \"{name}\"."),
253                        backrefs_on_msg,
254                    ));
255                }
256                (true, false) => {
257                    // Old explicit wins: only the new node is dupname'd.
258                    Self::dupname_new(node, &name);
259                    message = Some(dup_info(
260                        messages::INFO,
261                        format!("Duplicate implicit target name: \"{name}\"."),
262                        backrefs_on_msg,
263                    ));
264                }
265                (false, true) => {
266                    // New explicit overrides: old dupname'd, new keeps name.
267                    if let Some(old_id) = entry.id.clone() {
268                        self.fixups.push(DupnameFixup {
269                            name: name.clone(),
270                            node_id: old_id,
271                        });
272                    }
273                    self.nameids.insert(
274                        name.clone(),
275                        NameEntry {
276                            id: Some(id.clone()),
277                            explicit: true,
278                            refuri: refuri.map(str::to_string),
279                        },
280                    );
281                    message = Some(dup_info(
282                        messages::INFO,
283                        format!("Target name overrides implicit target name \"{name}\"."),
284                        false,
285                    ));
286                }
287                (false, false) => {
288                    if let Some(old_id) = entry.id.clone() {
289                        self.fixups.push(DupnameFixup {
290                            name: name.clone(),
291                            node_id: old_id,
292                        });
293                    }
294                    self.nameids.insert(
295                        name.clone(),
296                        NameEntry {
297                            id: None,
298                            explicit: false,
299                            refuri: None,
300                        },
301                    );
302                    Self::dupname_new(node, &name);
303                    message = Some(dup_info(
304                        messages::INFO,
305                        format!("Duplicate implicit target name: \"{name}\"."),
306                        backrefs_on_msg,
307                    ));
308                }
309            }
310        }
311        message
312    }
313
314    /// Register an implicit target (section). On duplicate: INFO/1 message
315    /// (placed by the caller inside the new section after its title), new
316    /// node dupname'd immediately, old node queued for
317    /// [`apply_dupname_fixups`].
318    pub fn set_id_implicit(&mut self, node: &mut Node, line: u32, source: &str) -> Option<Node> {
319        self.register(node, line, source, false, true, None)
320    }
321
322    /// Register an explicit target (`.. _name:` forms). On duplicate:
323    /// WARNING/2; `backrefs` appear on the message only for internal targets
324    /// (probe-verified: external/refuri duplicates carry no backrefs).
325    pub fn set_id_explicit(
326        &mut self,
327        node: &mut Node,
328        line: u32,
329        source: &str,
330        internal: bool,
331        refuri: Option<&str>,
332    ) -> Option<Node> {
333        self.register(node, line, source, true, internal, refuri)
334    }
335
336    /// Register an anonymous target: always an auto id, never a name.
337    pub fn set_id_anonymous(&mut self, node: &mut Node) {
338        let id = self.allocate_id(&[]);
339        node.attrs.ids.push(id);
340    }
341
342    pub fn take_fixups(&mut self) -> Vec<DupnameFixup> {
343        std::mem::take(&mut self.fixups)
344    }
345}
346
347/// Post-parse pass: move `name` from `names` to `dupnames` on the node
348/// carrying `node_id` (the FIRST occurrence keeps its id, loses its name).
349pub fn apply_dupname_fixups(root: &mut Node, fixups: &[DupnameFixup]) {
350    if fixups.is_empty() {
351        return;
352    }
353    for fixup in fixups {
354        apply_one_fixup(root, fixup);
355    }
356}
357
358fn apply_one_fixup(node: &mut Node, fixup: &DupnameFixup) -> bool {
359    if node.attrs.ids.contains(&fixup.node_id) {
360        if let Some(pos) = node.attrs.names.iter().position(|n| *n == fixup.name) {
361            node.attrs.names.remove(pos);
362            node.attrs.dupnames.push(fixup.name.clone());
363        }
364        return true;
365    }
366    node.children
367        .iter_mut()
368        .any(|child| apply_one_fixup(child, fixup))
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374    use crate::doctree::{kinds, AttrValue, Node, Span};
375
376    #[test]
377    fn make_id_basics() {
378        assert_eq!(make_id("My  Section    Title!"), "my-section-title");
379        assert_eq!(make_id("Hello World!"), "hello-world");
380        assert_eq!(make_id("1. Intro"), "intro");
381        assert_eq!(make_id("2026 report"), "report");
382        assert_eq!(make_id("Überblick"), "uberblick");
383        assert_eq!(make_id("straße"), "strasze");
384        assert_eq!(make_id("!!!"), "");
385        assert_eq!(make_id("123"), "");
386        assert_eq!(make_id("..."), "");
387    }
388
389    #[test]
390    fn name_normalization() {
391        assert_eq!(
392            fully_normalize_name("My  Phrase   Target"),
393            "my phrase target"
394        );
395        assert_eq!(fully_normalize_name("Hello World!"), "hello world!");
396        assert_eq!(fully_normalize_name("Überblick"), "überblick");
397        assert_eq!(whitespace_normalize_name("A  B"), "A B");
398    }
399
400    #[test]
401    fn registry_assigns_ids_and_handles_implicit_duplicates() {
402        let mut reg = IdRegistry::new();
403        let mut s1 = Node::elem(kinds::SECTION, Span::ZERO);
404        s1.attrs.names.push("duplicate".into());
405        assert!(reg.set_id_implicit(&mut s1, 3, "<snippet>").is_none());
406        assert_eq!(s1.attrs.ids, vec!["duplicate"]);
407
408        let mut s2 = Node::elem(kinds::SECTION, Span::ZERO);
409        s2.attrs.names.push("duplicate".into());
410        let msg = reg
411            .set_id_implicit(&mut s2, 7, "<snippet>")
412            .expect("dup INFO");
413        assert_eq!(s2.attrs.ids, vec!["id1"]);
414        assert!(s2.attrs.names.is_empty());
415        assert_eq!(s2.attrs.dupnames, vec!["duplicate"]);
416        assert_eq!(msg.get("type"), Some(&AttrValue::Str("INFO".into())));
417        assert_eq!(msg.get("line"), Some(&AttrValue::Int(7)));
418        assert_eq!(msg.attrs.backrefs, vec!["id1"]);
419
420        // The FIRST node's fixup is deferred (it lives in the tree):
421        let fixups = reg.take_fixups();
422        assert_eq!(
423            fixups,
424            vec![DupnameFixup {
425                name: "duplicate".into(),
426                node_id: "duplicate".into()
427            }]
428        );
429        let mut root = Node::elem(kinds::DOCUMENT, Span::ZERO);
430        root.children.push(s1);
431        apply_dupname_fixups(&mut root, &fixups);
432        let s1 = &root.children[0];
433        assert!(s1.attrs.names.is_empty());
434        assert_eq!(s1.attrs.dupnames, vec!["duplicate"]);
435        assert_eq!(s1.attrs.ids, vec!["duplicate"]); // keeps its id
436    }
437
438    #[test]
439    fn registry_auto_ids_for_unmakeable_names() {
440        let mut reg = IdRegistry::new();
441        for (i, title) in ["!!!", "123", "..."].iter().enumerate() {
442            let mut s = Node::elem(kinds::SECTION, Span::ZERO);
443            s.attrs.names.push(fully_normalize_name(title));
444            reg.set_id_implicit(&mut s, 1, "<snippet>");
445            assert_eq!(s.attrs.ids, vec![format!("id{}", i + 1)]);
446            assert_eq!(s.attrs.names.len(), 1); // names kept, no collision
447        }
448    }
449
450    #[test]
451    fn explicit_duplicate_warning_backrefs_only_when_internal() {
452        let mut reg = IdRegistry::new();
453        let mut t1 = Node::elem(kinds::TARGET, Span::ZERO);
454        t1.attrs.names.push("dup".into());
455        assert!(reg
456            .set_id_explicit(&mut t1, 1, "<snippet>", false, Some("https://1/"))
457            .is_none());
458
459        let mut t2 = Node::elem(kinds::TARGET, Span::ZERO);
460        t2.attrs.names.push("dup".into());
461        let msg = reg
462            .set_id_explicit(&mut t2, 3, "<snippet>", false, Some("https://2/"))
463            .expect("dup WARNING");
464        assert_eq!(msg.get("type"), Some(&AttrValue::Str("WARNING".into())));
465        assert!(msg.attrs.backrefs.is_empty()); // external: no backrefs
466        assert_eq!(t2.attrs.ids, vec!["id1"]);
467        assert_eq!(t2.attrs.dupnames, vec!["dup"]);
468
469        let mut reg = IdRegistry::new();
470        let mut i1 = Node::elem(kinds::TARGET, Span::ZERO);
471        i1.attrs.names.push("t".into());
472        reg.set_id_explicit(&mut i1, 1, "<snippet>", true, None);
473        let mut i2 = Node::elem(kinds::TARGET, Span::ZERO);
474        i2.attrs.names.push("t".into());
475        let msg = reg
476            .set_id_explicit(&mut i2, 5, "<snippet>", true, None)
477            .expect("dup WARNING");
478        assert_eq!(msg.attrs.backrefs, vec!["id1"]); // internal: backrefs
479    }
480}
sphinx_ultra/doctree/ids.rs

sphinx_ultra/doctree/
ids.rs
