use std::borrow::Cow;
use crate::error::{Error, Result};
use crate::text;
#[inline]
pub(crate) fn decode_entities(s: &str) -> Cow<'_, str> {
if memchr::memchr(b'&', s.as_bytes()).is_none() {
return Cow::Borrowed(s);
}
Cow::Owned(html_escape::decode_html_entities(s).into_owned())
}
const ATTR_VALUE_WEIGHT_CAP: u32 = 128;
const RAW_TEXT_ELEMENTS: &[&str] = &["script", "style"];
pub(crate) fn neutralise_raw_text(html: &str) -> Cow<'_, str> {
let bytes = html.as_bytes();
if !RAW_TEXT_ELEMENTS.iter().any(|t| find_tag(bytes, t, 0).is_some()) {
return Cow::Borrowed(html);
}
let mut out = String::with_capacity(html.len());
let mut cursor = 0;
while cursor < html.len() {
let Some((start, tag)) = RAW_TEXT_ELEMENTS
.iter()
.filter_map(|t| find_tag(bytes, t, cursor).map(|i| (i, *t)))
.min_by_key(|(i, _)| *i)
else {
break;
};
let Some(open_end) = end_of_open_tag(bytes, start) else { break };
out.push_str(&html[cursor..=open_end]);
let close = format!("</{tag}");
let body_end = find_ci(bytes, close.as_bytes(), open_end + 1).unwrap_or(html.len());
let keeps_body = html[start..=open_end].to_ascii_lowercase().contains("json");
if keeps_body {
out.push_str(&html[open_end + 1..body_end].replace('<', "<"));
}
cursor = body_end;
}
out.push_str(&html[cursor.min(html.len())..]);
Cow::Owned(out)
}
pub(crate) fn neutralise_bogus_markup(html: &str) -> Cow<'_, str> {
let bytes = html.as_bytes();
if find_bogus(bytes, 0).is_none() {
return Cow::Borrowed(html);
}
let mut out = String::with_capacity(html.len());
let mut cursor = 0;
while let Some(at) = find_bogus(bytes, cursor) {
out.push_str(&html[cursor..at]);
if bytes.get(at + 1) == Some(&b'?') {
cursor = match memchr::memchr(b'>', &bytes[at..]) {
Some(end) => at + end + 1,
None => html.len(),
};
} else {
out.push_str("<");
cursor = at + 1;
}
}
out.push_str(&html[cursor..]);
Cow::Owned(out)
}
fn find_bogus(bytes: &[u8], from: usize) -> Option<usize> {
let mut at = from;
while let Some(offset) = memchr::memchr(b'<', &bytes[at..]) {
let i = at + offset;
match bytes.get(i + 1) {
Some(b) if b.is_ascii_alphabetic() || *b == b'!' || *b == b'/' => at = i + 1,
None => return None,
_ => return Some(i),
}
}
None
}
fn find_tag(bytes: &[u8], name: &str, from: usize) -> Option<usize> {
let needle = format!("<{name}");
let mut at = from;
while let Some(i) = find_ci(bytes, needle.as_bytes(), at) {
match bytes.get(i + needle.len()) {
Some(b' ' | b'>' | b'/' | b'\t' | b'\n' | b'\r') => return Some(i),
_ => at = i + 1,
}
}
None
}
fn find_ci(haystack: &[u8], needle: &[u8], from: usize) -> Option<usize> {
if from >= haystack.len() {
return None;
}
let first = needle[0].to_ascii_lowercase();
let mut at = from;
while at + needle.len() <= haystack.len() {
let i = memchr::memchr2(first, first.to_ascii_uppercase(), &haystack[at..])? + at;
if i + needle.len() > haystack.len() {
return None;
}
if haystack[i..i + needle.len()].eq_ignore_ascii_case(needle) {
return Some(i);
}
at = i + 1;
}
None
}
fn end_of_open_tag(bytes: &[u8], start: usize) -> Option<usize> {
let mut quote = None;
for (offset, &b) in bytes[start..].iter().enumerate() {
match (quote, b) {
(Some(q), c) if c == q => quote = None,
(None, b'"' | b'\'') => quote = Some(b),
(None, b'>') => return Some(start + offset),
_ => {}
}
}
None
}
pub(crate) type Id = usize;
pub(crate) const INVISIBLE_TAGS: &[&str] =
&["script", "style", "noscript", "template", "svg", "canvas"];
pub(crate) const BLOCK_TAGS: &[&str] = &[
"address",
"article",
"aside",
"blockquote",
"details",
"div",
"dl",
"dd",
"dt",
"fieldset",
"figcaption",
"figure",
"footer",
"form",
"h1",
"h2",
"h3",
"h4",
"h5",
"h6",
"header",
"hgroup",
"hr",
"li",
"main",
"nav",
"ol",
"p",
"pre",
"section",
"table",
"tbody",
"td",
"tfoot",
"th",
"thead",
"tr",
"ul",
];
pub(crate) struct Doc<'a> {
pub(crate) dom: tl::VDom<'a>,
parent: Vec<Option<Id>>,
names: Vec<Box<str>>,
bytes: Vec<u32>,
text_len: Vec<u32>,
link_len: Vec<u32>,
pub(crate) preorder: Vec<Id>,
document_text: u32,
}
impl<'a> Doc<'a> {
pub(crate) fn parse(html: &'a str) -> Result<Doc<'a>> {
let dom = tl::parse(html, tl::ParserOptions::default())
.map_err(|e| Error::Parse(e.to_string()))?;
let n = dom.nodes().len();
let mut parent = vec![None; n];
let mut names: Vec<Box<str>> = vec![Box::from(""); n];
let mut seen = vec![false; n];
let mut preorder = Vec::with_capacity(n);
let mut stack: Vec<(Id, Option<Id>)> =
dom.children().iter().rev().map(|h| (h.get_inner() as Id, None)).collect();
while let Some((id, par)) = stack.pop() {
if id >= n || seen[id] {
continue; }
seen[id] = true;
parent[id] = par;
if let Some(tag) = dom.nodes().get(id).and_then(|node| node.as_tag()) {
names[id] = Box::from(tag.name().as_utf8_str().to_ascii_lowercase().as_str());
}
preorder.push(id);
if let Some(node) = dom.nodes().get(id)
&& let Some(children) = node.children()
{
for h in children.top().as_slice().iter().rev() {
stack.push((h.get_inner() as Id, Some(id)));
}
}
}
let mut text_len = vec![0u32; n];
let mut link_len = vec![0u32; n];
let mut bytes = vec![0u32; n];
for &id in preorder.iter().rev() {
let node = match dom.nodes().get(id) {
Some(node) => node,
None => continue,
};
match node {
tl::Node::Raw(raw_bytes) => {
let raw = raw_bytes.as_utf8_str();
let decoded = decode_entities(&raw);
text_len[id] = text::visible_len(decoded.trim()) as u32;
bytes[id] = bytes[id].saturating_add(raw.len() as u32);
}
tl::Node::Tag(tag) => {
let name = tag.name().as_utf8_str();
let mut own = 2 * name.len() as u32 + 4;
for (key, value) in tag.attributes().iter() {
own = own.saturating_add(key.len() as u32 + 4);
let len = value.map(|v| v.len() as u32).unwrap_or(0);
own = own.saturating_add(len.min(ATTR_VALUE_WEIGHT_CAP));
}
bytes[id] = bytes[id].saturating_add(own);
if INVISIBLE_TAGS.contains(&name.as_ref()) {
text_len[id] = 0;
link_len[id] = 0;
} else if name == "a" {
link_len[id] = text_len[id];
}
}
tl::Node::Comment(c) => {
text_len[id] = 0;
bytes[id] = c.as_bytes().len() as u32 + 7;
}
}
if let Some(p) = parent[id] {
text_len[p] = text_len[p].saturating_add(text_len[id]);
link_len[p] = link_len[p].saturating_add(link_len[id]);
bytes[p] = bytes[p].saturating_add(bytes[id]);
}
}
let document_text = preorder
.iter()
.copied()
.find(|&id| {
dom.nodes()
.get(id)
.and_then(|n| n.as_tag())
.is_some_and(|t| t.name().as_utf8_str().eq_ignore_ascii_case("body"))
})
.map(|body| text_len[body])
.unwrap_or_else(|| preorder.first().map(|&r| text_len[r]).unwrap_or(0));
Ok(Doc { dom, parent, names, bytes, text_len, link_len, preorder, document_text })
}
pub(crate) fn is_dominant(&self, id: Id) -> bool {
self.document_text > 0 && self.text_len(id) as u64 * 2 > self.document_text as u64
}
#[inline]
pub(crate) fn node(&self, id: Id) -> Option<&tl::Node<'a>> {
self.dom.nodes().get(id)
}
#[inline]
pub(crate) fn tag(&self, id: Id) -> Option<&tl::HTMLTag<'a>> {
self.node(id)?.as_tag()
}
#[inline]
pub(crate) fn tag_name(&self, id: Id) -> &str {
self.names.get(id).map(|s| &**s).unwrap_or("")
}
#[inline]
pub(crate) fn parent(&self, id: Id) -> Option<Id> {
self.parent.get(id).copied().flatten()
}
#[inline]
pub(crate) fn text_len(&self, id: Id) -> u32 {
self.text_len.get(id).copied().unwrap_or(0)
}
pub(crate) fn link_density(&self, id: Id) -> f32 {
let text = self.text_len(id);
if text == 0 {
return 0.0;
}
(self.link_len.get(id).copied().unwrap_or(0) as f32 / text as f32).min(1.0)
}
#[inline]
pub(crate) fn html_len(&self, id: Id) -> u32 {
self.bytes.get(id).copied().unwrap_or(0)
}
pub(crate) fn text_ratio(&self, id: Id) -> f32 {
let html = self.html_len(id);
if html == 0 {
return 0.0;
}
(self.text_len(id) as f32 / html as f32).min(1.0)
}
pub(crate) fn children(&self, id: Id) -> Vec<Id> {
self.node(id)
.and_then(|n| n.children())
.map(|c| c.top().as_slice().iter().map(|h| h.get_inner() as Id).collect())
.unwrap_or_default()
}
pub(crate) fn descendants(&self, id: Id) -> Vec<Id> {
let mut out = Vec::new();
let mut stack = vec![id];
while let Some(cur) = stack.pop() {
out.push(cur);
let kids = self.children(cur);
for k in kids.into_iter().rev() {
stack.push(k);
}
}
out
}
pub(crate) fn attr(&self, id: Id, key: &str) -> Option<String> {
let tag = self.tag(id)?;
let value = tag.attributes().get(key)??;
let raw = value.as_utf8_str();
Some(decode_entities(&raw).into_owned())
}
pub(crate) fn signature(&self, id: Id) -> String {
let mut sig = String::new();
if let Some(tag) = self.tag(id) {
if let Some(c) = tag.attributes().class() {
sig.push_str(&c.as_utf8_str().to_ascii_lowercase());
sig.push(' ');
}
if let Some(i) = tag.attributes().id() {
sig.push_str(&i.as_utf8_str().to_ascii_lowercase());
sig.push(' ');
}
for key in ["role", "data-testid", "aria-label", "itemprop"] {
if let Some(Some(v)) = tag.attributes().get(key) {
sig.push_str(&v.as_utf8_str().to_ascii_lowercase());
sig.push(' ');
}
}
for (key, _) in tag.attributes().iter() {
let key = key.to_ascii_lowercase();
if key.starts_with("data-ad") || key.starts_with("data-google-ad") {
sig.push_str("advertisement ");
break;
}
}
}
sig
}
pub(crate) fn inner_text(&self, id: Id) -> String {
let mut buf = String::new();
for d in self.descendants(id) {
match self.node(d) {
Some(tl::Node::Raw(bytes)) => {
if self.has_invisible_ancestor(d, id) {
continue;
}
let raw = bytes.as_utf8_str();
buf.push_str(&decode_entities(&raw));
buf.push(' ');
}
Some(tl::Node::Tag(tag)) => {
if matches!(tag.name().as_utf8_str().as_ref(), "br" | "p" | "div" | "li") {
buf.push('\n');
}
}
_ => {}
}
}
text::normalize_ws(&buf)
}
pub(crate) fn raw_text(&self, id: Id) -> String {
let mut buf = String::new();
for d in self.descendants(id) {
if let Some(tl::Node::Raw(bytes)) = self.node(d) {
let raw = bytes.as_utf8_str();
buf.push_str(&decode_entities(&raw));
}
}
buf
}
pub(crate) fn is_leaf_block(&self, id: Id) -> bool {
self.descendants(id).into_iter().skip(1).all(|d| !BLOCK_TAGS.contains(&self.tag_name(d)))
}
fn has_invisible_ancestor(&self, mut id: Id, stop: Id) -> bool {
while let Some(p) = self.parent(id) {
if INVISIBLE_TAGS.contains(&self.tag_name(p)) {
return true;
}
if p == stop {
return false;
}
id = p;
}
false
}
pub(crate) fn ancestors(&self, id: Id, levels: usize) -> Vec<Id> {
let mut out = Vec::with_capacity(levels);
let mut cur = id;
for _ in 0..levels {
match self.parent(cur) {
Some(p) => {
out.push(p);
cur = p;
}
None => break,
}
}
out
}
}
#[cfg(test)]
mod tests {
use super::*;
const HTML: &str = r#"<html><body>
<nav><a href="/a">A</a><a href="/b">B</a><a href="/c">C</a></nav>
<article><p>Real prose with several words in it.</p></article>
<script>var noise = "should not count";</script>
</body></html>"#;
fn find<'d>(doc: &Doc<'d>, name: &str) -> Id {
doc.preorder.iter().copied().find(|&id| doc.tag_name(id) == name).expect("tag present")
}
#[test]
fn link_density_separates_nav_from_prose() {
let doc = Doc::parse(HTML).unwrap();
let nav = find(&doc, "nav");
let article = find(&doc, "article");
assert!(doc.link_density(nav) > 0.99, "nav was {}", doc.link_density(nav));
assert_eq!(doc.link_density(article), 0.0);
}
#[test]
fn script_text_is_not_counted() {
let doc = Doc::parse(HTML).unwrap();
let script = find(&doc, "script");
assert_eq!(doc.text_len(script), 0);
assert!(!doc.inner_text(find(&doc, "body")).contains("should not count"));
}
#[test]
fn subtree_bytes_reflect_the_whole_subtree() {
let doc = Doc::parse(HTML).unwrap();
let body = find(&doc, "body");
let article = find(&doc, "article");
let p = find(&doc, "p");
assert!(doc.html_len(body) > doc.html_len(article));
assert!(doc.html_len(article) > doc.html_len(p));
assert!(doc.html_len(p) >= doc.text_len(p));
assert!(doc.text_ratio(p) > 0.3, "{}", doc.text_ratio(p));
}
#[test]
fn parents_and_document_order_are_consistent() {
let doc = Doc::parse(HTML).unwrap();
let article = find(&doc, "article");
let p = find(&doc, "p");
assert_eq!(doc.parent(p), Some(article));
let pos = |id: Id| doc.preorder.iter().position(|&x| x == id).unwrap();
assert!(pos(article) < pos(p), "ancestors must precede descendants");
}
}
#[cfg(test)]
mod bogus_markup_tests {
use super::neutralise_bogus_markup;
use std::borrow::Cow;
#[test]
fn a_bogus_comment_is_removed_not_left_open() {
assert_eq!(neutralise_bogus_markup("<p>a</p><?><p>b</p>"), "<p>a</p><p>b</p>");
assert_eq!(neutralise_bogus_markup("<div><?php echo $x; ?>t</div>"), "<div>t</div>");
}
#[test]
fn an_unterminated_bogus_comment_eats_only_itself() {
assert_eq!(neutralise_bogus_markup("<p>a</p><?php echo"), "<p>a</p>");
}
#[test]
fn punctuation_after_a_bracket_is_text_not_a_tag() {
assert_eq!(neutralise_bogus_markup("<div><%= name %></div>"), "<div><%= name %></div>");
assert_eq!(neutralise_bogus_markup("i <3 it"), "i <3 it");
assert_eq!(neutralise_bogus_markup("a < b"), "a < b");
}
#[test]
fn real_markup_is_untouched() {
for html in [
"<p class='x'>hi</p>",
"<!-- comment --><!doctype html><P>hi</P>",
"<![CDATA[x]]>",
"</div>",
] {
assert!(matches!(neutralise_bogus_markup(html), Cow::Borrowed(_)), "{html}");
}
}
#[test]
fn a_trailing_bracket_is_left_alone() {
assert!(matches!(neutralise_bogus_markup("text <"), Cow::Borrowed(_)));
}
}
#[cfg(test)]
mod raw_text_tests {
use super::neutralise_raw_text;
#[test]
fn a_comparison_in_a_script_no_longer_opens_a_tag() {
for js in ["for(i=0;i<n;i++){}", "if(a<1){}", "x()<e.timestamp+1", "a<b&&c<d"] {
let html = format!("<html><body><script>{js}</script><div>KEEP</div></body></html>");
let out = neutralise_raw_text(&html);
assert!(!out.contains(js), "script body survived: {out}");
assert!(out.contains("<div>KEEP</div>"), "document truncated: {out}");
}
}
#[test]
fn json_ld_survives_escaped() {
let html = r#"<script type="application/ld+json">{"name":"a<b"}</script>"#;
let out = neutralise_raw_text(html);
assert!(out.contains(r#"{"name":"a<b"}"#), "{out}");
}
#[test]
fn style_bodies_go_too() {
let html = "<style>.a{color:red}</style><p>x</p>";
let out = neutralise_raw_text(html);
assert!(!out.contains("color:red"));
assert!(out.contains("<p>x</p>"));
}
#[test]
fn handles_the_awkward_shapes() {
let out = neutralise_raw_text(r#"<SCRIPT TYPE="text/javascript">a<b</SCRIPT><p>x</p>"#);
assert!(out.contains("<p>x</p>"), "{out}");
let out = neutralise_raw_text(r#"<script data-x="a>b">i<n</script><p>y</p>"#);
assert!(out.contains("<p>y</p>"), "{out}");
let out = neutralise_raw_text("<script>unterminated i<n");
assert!(!out.contains("i<n"), "{out}");
}
#[test]
fn no_raw_text_elements_means_no_allocation() {
let html = "<html><body><p>plain</p></body></html>";
assert!(matches!(neutralise_raw_text(html), std::borrow::Cow::Borrowed(_)));
}
#[test]
fn only_matches_whole_tag_names() {
let html = "<styleguide>a<b</styleguide><p>z</p>";
assert!(matches!(neutralise_raw_text(html), std::borrow::Cow::Borrowed(_)));
}
}