webfetch/
limits.rs

1//! A pre-parse bound on document complexity.
2//!
3//! html5ever's tree builder rescans its stack of open elements when it inserts
4//! certain tags, so parse time grows quadratically with nesting depth. Measured
5//! on this crate: 4 000 nested `<div>`s parse in 0.09 s, 16 000 in 1.7 s, and
6//! 200 000 — a 2.2 MB file, comfortably inside the 5 MiB body cap — took over
7//! four minutes. Neither the body cap nor `--timeout` helps: the cap counts
8//! bytes, and the timeout covers the HTTP request, not the parse that follows.
9//! On the MCP server that stall blocks every other request.
10//!
11//! So depth is measured up front, in one linear scan, and a document past the
12//! limit is refused rather than parsed. Real pages sit around depth 20-50;
13//! [`MAX_NESTING_DEPTH`] is far above anything a document written for humans
14//! reaches, so the check only fires on pathological input.
15
16/// Nesting depth past which a document is refused.
17pub const MAX_NESTING_DEPTH: usize = 10_000;
18
19/// HTML void elements: they never open a level.
20const VOID_ELEMENTS: [&str; 14] = [
21    "area", "base", "br", "col", "embed", "hr", "img", "input", "link", "meta", "param", "source",
22    "track", "wbr",
23];
24
25/// Estimate a document's maximum element nesting depth.
26///
27/// A tag scan, not a parse — the whole point is to answer before paying for a
28/// parse. It ignores the implicit closes a real parser performs (`<p>` inside
29/// `<p>`, unclosed `<li>`), so it can *over*-estimate on sloppy markup; that is
30/// the safe direction only because the limit sits so far above real documents.
31pub fn max_nesting_depth(html: &str) -> usize {
32    let bytes = html.as_bytes();
33    let mut depth: isize = 0;
34    let mut max: isize = 0;
35    let mut i = 0;
36
37    while i < bytes.len() {
38        if bytes[i] != b'<' {
39            i += 1;
40            continue;
41        }
42        let Some(next) = bytes.get(i + 1) else { break };
43
44        // Comments, doctypes and processing instructions open nothing. A
45        // comment ends at `-->`, not at the first `>` — markup inside one must
46        // not be counted.
47        if bytes[i..].starts_with(b"<!--") {
48            i = match find_slice(bytes, i + 4, b"-->") {
49                Some(end) => end + 3,
50                None => break,
51            };
52            continue;
53        }
54        if matches!(next, b'!' | b'?') {
55            i = match find_byte(bytes, i, b'>') {
56                Some(end) => end + 1,
57                None => break,
58            };
59            continue;
60        }
61
62        let closing = *next == b'/';
63        let name_start = if closing { i + 2 } else { i + 1 };
64        let mut name_end = name_start;
65        while name_end < bytes.len() && bytes[name_end].is_ascii_alphanumeric() {
66            name_end += 1;
67        }
68        if name_end == name_start {
69            i += 1;
70            continue;
71        }
72        let Some(tag_end) = find_byte(bytes, name_end, b'>') else {
73            break;
74        };
75        let name = html[name_start..name_end].to_ascii_lowercase();
76        let self_closing = tag_end > 0 && bytes[tag_end - 1] == b'/';
77
78        if closing {
79            depth -= 1;
80        } else if !self_closing && !VOID_ELEMENTS.contains(&name.as_str()) {
81            depth += 1;
82            max = max.max(depth);
83        }
84        i = tag_end + 1;
85    }
86
87    max.max(0) as usize
88}
89
90/// Is this document too deeply nested to parse within a sane time budget?
91pub fn too_deeply_nested(html: &str) -> Option<usize> {
92    let depth = max_nesting_depth(html);
93    (depth > MAX_NESTING_DEPTH).then_some(depth)
94}
95
96fn find_byte(bytes: &[u8], from: usize, needle: u8) -> Option<usize> {
97    bytes[from..]
98        .iter()
99        .position(|b| *b == needle)
100        .map(|p| p + from)
101}
102
103fn find_slice(bytes: &[u8], from: usize, needle: &[u8]) -> Option<usize> {
104    if from >= bytes.len() {
105        return None;
106    }
107    bytes[from..]
108        .windows(needle.len())
109        .position(|w| w == needle)
110        .map(|p| p + from)
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn ordinary_documents_are_shallow() {
119        let html = "<html><body><div><section><article><p>Hi <b>there</b></p>\
120                    </article></section></div></body></html>";
121        assert!(max_nesting_depth(html) < 10, "{}", max_nesting_depth(html));
122        assert_eq!(too_deeply_nested(html), None);
123    }
124
125    #[test]
126    fn void_and_self_closing_tags_do_not_nest() {
127        let html = "<div><br><img src=x><hr><input><meta charset=utf-8><span/></div>";
128        assert_eq!(max_nesting_depth(html), 1);
129    }
130
131    #[test]
132    fn comments_and_doctype_are_ignored() {
133        let html = "<!DOCTYPE html><!-- <div><div><div> --><p>x</p>";
134        assert_eq!(max_nesting_depth(html), 1);
135    }
136
137    #[test]
138    fn depth_is_counted() {
139        let n = 500;
140        let html = format!("{}<p>x</p>{}", "<div>".repeat(n), "</div>".repeat(n));
141        assert_eq!(max_nesting_depth(&html), n + 1);
142    }
143
144    #[test]
145    fn pathological_nesting_is_refused() {
146        let n = MAX_NESTING_DEPTH + 1;
147        let html = format!("{}text{}", "<div>".repeat(n), "</div>".repeat(n));
148        assert_eq!(too_deeply_nested(&html), Some(n));
149    }
150}
webfetch/limits.rs

webfetch/
limits.rs
