src/skeleton.rs

  1//! HTML → semantic skeleton reduction.
  2//!
  3//! Two HTML exporters that agree on what a document *means* will still disagree on how
  4//! they wrap it: org buries every section in `outline-container` divs keyed by generated
  5//! ids, syntect emits one `<span>` per code token, and each backend picks its own class
  6//! names. Byte equality therefore measures nothing. The skeleton throws all of that away
  7//! and keeps the part worth comparing: the ordered sequence of element opens, element
  8//! closes, and text runs, with `<div>`/`<span>` dropped, every attribute except
  9//! `href`/`src` removed, whitespace collapsed, and entities decoded.
 10//!
 11//! This is the comparison primitive behind two things at once: orgo's differential check
 12//! against Emacs (`tests/oracle.rs`), and the cross-language conformance corpus, where an
 13//! implementation in another language ports [`skeleton`] and asserts its output matches
 14//! orgo's checked-in golden skeleton. Keeping one implementation here, rather than a copy
 15//! per consumer, is the point — the reduction *is* the contract, so it must be identical
 16//! everywhere.
 17
 18/// Elements dropped from the skeleton entirely, because once attributes are gone they
 19/// carry no meaning two exporters could agree or disagree *about*.
 20///
 21/// `div` is pure layout: org wraps every section in `outline-container`/`outline-text`
 22/// wrappers and we emit none. `span` is the same story at the inline level, and matters
 23/// far more than it looks: syntect emits one span per code token, so keeping them made a
 24/// source block contribute ~60 skeleton lines of pure noise and dragged the agreement on
 25/// `blocks.org` down to 36% — a number that said nothing about whether we render blocks
 26/// correctly. Text still carries the signal: a `<span class="todo">` shows up as its
 27/// text, `"TODO"`, which is the part worth comparing.
 28const IGNORED: &[&str] = &["div", "span"];
 29
 30/// Attributes kept in the skeleton. Ids and classes are generated (`org6c28c1b`) or
 31/// cosmetic (`org-ul`); `href` and `src` are the content.
 32const KEPT_ATTRS: &[&str] = &["href", "src"];
 33
 34/// The named references this reduction understands. HTML5 decodes a legacy set of them
 35/// without the closing semicolon, and org relies on that: `ox-html` 9.8 writes the
 36/// heading tag prefix as `&nbsp;&nbsp;&nbsp`. No name here is a prefix of another, so the
 37/// longest match is the only match.
 38const NAMED: &[(&str, char)] = &[
 39    ("amp", '&'),
 40    ("lt", '<'),
 41    ("gt", '>'),
 42    ("quot", '"'),
 43    ("apos", '\''),
 44    ("nbsp", '\u{a0}'),
 45];
 46
 47/// HTML void elements, which never emit a close event.
 48const VOID: &[&str] = &[
 49    "br", "hr", "img", "input", "meta", "link", "col", "area", "base", "source", "wbr",
 50];
 51
 52/// Reduce an HTML fragment to its semantic skeleton: one line per element open, element
 53/// close, or text run.
 54pub fn skeleton(html: &str) -> Vec<String> {
 55    let mut out = Vec::new();
 56    let chars: Vec<char> = html.chars().collect();
 57    let mut i = 0;
 58    let mut text = String::new();
 59
 60    while i < chars.len() {
 61        if chars[i] != '<' {
 62            text.push(chars[i]);
 63            i += 1;
 64            continue;
 65        }
 66        let Some(end) = find_from(&chars, i, ">") else {
 67            break;
 68        };
 69        // Comments and doctypes carry nothing.
 70        let is_markup_declaration = chars[i..].starts_with(&['<', '!']);
 71        let raw: String = chars[i + 1..end].iter().collect();
 72        i = end + 1;
 73        if is_markup_declaration {
 74            continue;
 75        }
 76        // Text is flushed only when a tag is actually *emitted*. Text either side of an
 77        // ignored tag therefore merges into one run, which is what makes a highlighted
 78        // source block compare as the one string of code it is, rather than as a
 79        // token-by-token sequence that has to line up exactly.
 80        if let Some(event) = tag_event(&raw) {
 81            flush_text(&mut text, &mut out);
 82            out.push(event);
 83        }
 84    }
 85    flush_text(&mut text, &mut out);
 86    out
 87}
 88
 89/// The skeleton line for one tag, given the text between its `<` and `>`, or `None`
 90/// for a tag the skeleton drops.
 91fn tag_event(raw: &str) -> Option<String> {
 92    let raw = raw.trim().trim_end_matches('/').trim();
 93    if let Some(name) = raw.strip_prefix('/') {
 94        let name = name.trim().to_ascii_lowercase();
 95        let dropped = IGNORED.contains(&name.as_str()) || VOID.contains(&name.as_str());
 96        return (!dropped).then(|| format!("</{name}>"));
 97    }
 98    let mut parts = raw.splitn(2, char::is_whitespace);
 99    let name = parts.next().unwrap_or("").to_ascii_lowercase();
100    if name.is_empty() || IGNORED.contains(&name.as_str()) {
101        return None;
102    }
103    let attrs = kept_attributes(parts.next().unwrap_or(""));
104    Some(format!("<{name}{attrs}>"))
105}
106
107fn flush_text(text: &mut String, out: &mut Vec<String>) {
108    let decoded = decode_entities(text);
109    let collapsed = decoded.split_whitespace().collect::<Vec<_>>().join(" ");
110    if !collapsed.is_empty() {
111        out.push(format!("{collapsed:?}"));
112    }
113    text.clear();
114}
115
116fn find_from(chars: &[char], from: usize, needle: &str) -> Option<usize> {
117    let n: Vec<char> = needle.chars().collect();
118    (from..chars.len()).find(|&k| chars[k..].starts_with(&n[..]))
119}
120
121/// Keep only the content-bearing attributes, in a stable order.
122fn kept_attributes(rest: &str) -> String {
123    let mut kept: Vec<(String, String)> = Vec::new();
124    for attr in KEPT_ATTRS {
125        if let Some(value) = attribute_value(rest, attr) {
126            kept.push(((*attr).to_string(), value));
127        }
128    }
129    kept.iter()
130        .map(|(k, v)| format!(" {k}=\"{}\"", decode_entities(v)))
131        .collect()
132}
133
134fn attribute_value(rest: &str, name: &str) -> Option<String> {
135    let mut search = rest;
136    while let Some(pos) = search.find(name) {
137        let before_ok = pos == 0
138            || search[..pos]
139                .chars()
140                .next_back()
141                .is_some_and(char::is_whitespace);
142        let after = &search[pos + name.len()..];
143        let after_trimmed = after.trim_start();
144        if before_ok && after_trimmed.starts_with('=') {
145            let value = after_trimmed[1..].trim_start();
146            let quote = value.chars().next()?;
147            if quote == '"' || quote == '\'' {
148                let end = value[1..].find(quote)? + 1;
149                return Some(value[1..end].to_string());
150            }
151            let end = value.find(char::is_whitespace).unwrap_or(value.len());
152            return Some(value[..end].to_string());
153        }
154        search = &search[pos + name.len()..];
155    }
156    None
157}
158
159/// Decode the entities either exporter is likely to emit, so an encoding difference is
160/// never reported as a semantic one.
161pub fn decode_entities(s: &str) -> String {
162    let mut out = String::with_capacity(s.len());
163    let mut rest = s;
164    while let Some(amp) = rest.find('&') {
165        out.push_str(&rest[..amp]);
166        let tail = &rest[amp..];
167        match entity_at(tail) {
168            Some((c, len)) => {
169                // A non-breaking space is a space for comparison purposes.
170                out.push(if c == '\u{a0}' { ' ' } else { c });
171                rest = &tail[len..];
172            }
173            None => {
174                out.push('&');
175                rest = &tail[1..];
176            }
177        }
178    }
179    out.push_str(rest);
180    out
181}
182
183/// The reference at the start of `tail`, which begins with `&`: the character it denotes
184/// and the bytes it occupies. The semicolon is optional for [`NAMED`], so `&nbsptag1`
185/// reads as a non-breaking space followed by `tag1`, the same way a browser reads it.
186fn entity_at(tail: &str) -> Option<(char, usize)> {
187    if let Some(semi) = tail.find(';').filter(|s| *s <= 12) {
188        if let Some(c) = named(&tail[1..semi]).or_else(|| numeric(&tail[1..semi])) {
189            return Some((c, semi + 1));
190        }
191    }
192    NAMED
193        .iter()
194        .find(|(name, _)| tail[1..].starts_with(name))
195        .map(|(name, c)| (*c, 1 + name.len()))
196}
197
198fn named(name: &str) -> Option<char> {
199    NAMED.iter().find(|(n, _)| *n == name).map(|(_, c)| *c)
200}
201
202fn numeric(name: &str) -> Option<char> {
203    name.strip_prefix('#')
204        .and_then(|n| match n.strip_prefix(['x', 'X']) {
205            Some(hex) => u32::from_str_radix(hex, 16).ok(),
206            None => n.parse::<u32>().ok(),
207        })
208        .and_then(char::from_u32)
209}
210