Skip to main content

muskitty_css_parser/
token_stream.rs

1//! Token stream (§5.3 L1722-1814).
2//!
3//! A token stream is a struct representing a stream of tokens and/or
4//! component values. It has three fields: `tokens` (a list), `index`
5//! (current position), and `marked_indexes` (a stack of saved positions
6//! for backtracking).
7
8use crate::types::ParseError;
9use muskitty_css_tokenizer::{CssTokenizer, Token, Tokenizer};
10use std::cell::{Cell, RefCell};
11
12/// §5.5 解析器最大嵌套深度。
13///
14/// `consume_a_simple_block` / `consume_a_function` 通过
15/// `consume_a_component_value` 间接递归;恶意 CSS(如 10,000 层
16/// `{{{{...}}}}` 或 `((((...))))`)可触发栈溢出。此上限用于在
17/// 递归到达危险深度前停止下降,记录 [`ParseError::NestingTooDeep`]。
18///
19/// 参考实现:
20/// - Chromium `kMaxCSSTokenizerNestingLevel = 100`
21/// - Firefox `kMaxNesting = 200`
22/// - Servo `MAX_PARSER_NESTING_DEPTH = 100`
23///
24/// 审计 F-3:1024 远超所有主流实现(5-10 倍),且每层在语法解析 + 下游
25/// (calc 求值、选择器解析)各叠 ~2-3 帧调用栈,1000 层即逼近线程栈余量。
26/// 取 Firefox 的 200,与最宽的主流上限平齐。
27///
28/// [`ParseError::NestingTooDeep`]: crate::types::ParseError::NestingTooDeep
29pub const MAX_NESTING_DEPTH: u32 = 200;
30
31/// §5.3 L1725-1754: A token stream.
32#[derive(Debug, Clone)]
33pub struct TokenStream {
34    /// §5.3 L1730-1738: A list of tokens and/or component values. We
35    /// model component values as `Token`s here for simplicity; the
36    /// §5.5 algorithms that consume "component values" wrap tokens
37    /// into [`crate::types::ComponentValue`] at the boundary.
38    pub tokens: Vec<Token>,
39    /// §5.3 L1740-1748: An index into `tokens`, representing parsing
40    /// progress. Starts at 0. Never decreases except via
41    /// [`Self::restore_mark`].
42    pub index: usize,
43    /// §5.3 L1750-1753: A stack of index values for backtracking.
44    /// Starts empty.
45    marked_indexes: Vec<usize>,
46    /// 与 `tokens` 平行的 byte ranges。空 Vec 表示无 source tracking
47    /// (`new()` 构造的 stream 无 source)。由 [`Self::with_source`] 填充。
48    token_spans: Vec<std::ops::Range<usize>>,
49    /// 原始 source text。`None` 表示无 source tracking。
50    source: Option<String>,
51    /// §5.5 递归保护:当前嵌套深度(`consume_a_simple_block` /
52    /// `consume_a_function` 的递归深度)。进入 +1,退出 -1。
53    depth: Cell<u32>,
54    /// 嵌套深度超限时记录的错误。解析继续(按 §5.5 错误恢复语义
55    /// 停止下降),调用方可通过 [`Self::nesting_error`] 读取。
56    nesting_error: RefCell<Option<ParseError>>,
57}
58
59impl TokenStream {
60    /// §5.3: Construct a new token stream over `tokens`. The stream
61    /// implicitly appends an EOF token (§5.3 L1811-1813); we model
62    /// it by returning `Token::Eof` from [`Self::next_token`] when
63    /// index is out of bounds, rather than storing a sentinel.
64    ///
65    /// 构造的 stream **不带** source-text tracking。如需追踪原始 source
66    /// (用于 §5.5.6 `original_text`),请用 [`Self::with_source`]。
67    pub fn new(mut tokens: Vec<Token>) -> Self {
68        // Ensure an EOF token is present at the end (§5.3 L1811-1813).
69        // The tokenizer already emits one, but be defensive.
70        if tokens.last().is_none_or(|t| !matches!(t, Token::Eof)) {
71            tokens.push(Token::Eof);
72        }
73        Self {
74            tokens,
75            index: 0,
76            marked_indexes: Vec::new(),
77            token_spans: Vec::new(),
78            source: None,
79            depth: Cell::new(0),
80            nesting_error: RefCell::new(None),
81        }
82    }
83
84    /// 构造一个带 source-text tracking 的 TokenStream。
85    ///
86    /// tokenize `source` 并记录每个 token 的 byte range,使
87    /// [`Self::source_slice`] 能返回原始 source 片段。供 §5.5.6
88    /// `original_text`(custom property)使用。
89    pub fn with_source(source: &str) -> Self {
90        let mut tz = CssTokenizer::new(source);
91        // 建立 char-index → byte-offset 映射(tokenizer 内部用 char 索引)
92        let char_to_byte: Vec<usize> = source.char_indices().map(|(i, _)| i).collect();
93        let source_len = source.len();
94
95        let mut tokens = Vec::new();
96        let mut spans = Vec::new();
97        while let Some((token, char_range)) = tz.next_token_with_span() {
98            let start_byte = char_to_byte
99                .get(char_range.start)
100                .copied()
101                .unwrap_or(source_len);
102            let end_byte = char_to_byte
103                .get(char_range.end)
104                .copied()
105                .unwrap_or(source_len);
106            let is_eof = matches!(token, Token::Eof);
107            tokens.push(token);
108            spans.push(start_byte..end_byte);
109            if is_eof {
110                break;
111            }
112        }
113        // 防御:确保 EOF 存在(与 new() 一致)
114        if tokens.last().is_none_or(|t| !matches!(t, Token::Eof)) {
115            tokens.push(Token::Eof);
116            spans.push(source_len..source_len);
117        }
118        Self {
119            tokens,
120            index: 0,
121            marked_indexes: Vec::new(),
122            token_spans: spans,
123            source: Some(source.to_string()),
124            depth: Cell::new(0),
125            nesting_error: RefCell::new(None),
126        }
127    }
128
129    /// 记录嵌套深度超限错误(仅首次覆盖,保留最早的超限点)。
130    pub fn record_nesting_error(&self, depth: u32) {
131        if self.nesting_error.borrow().is_none() {
132            self.nesting_error.replace(Some(ParseError::NestingTooDeep {
133                depth,
134                limit: MAX_NESTING_DEPTH,
135            }));
136        }
137    }
138
139    /// 返回解析过程中记录的第一个嵌套深度超限错误。
140    pub fn nesting_error(&self) -> Option<ParseError> {
141        self.nesting_error.borrow().clone()
142    }
143
144    /// 进入一层嵌套(`consume_a_simple_block` / `consume_a_function`
145    /// 入口调用)。
146    ///
147    /// 返回 `Some(depth)` 表示该层已超过 [`MAX_NESTING_DEPTH`]:
148    /// 错误已被记录,调用方应停止下降(不再递归)并返回空结果。
149    /// 返回 `None` 表示正常进入。
150    pub fn enter_nesting(&self) -> Option<u32> {
151        let depth = self.depth.get() + 1;
152        self.depth.set(depth);
153        if depth > MAX_NESTING_DEPTH {
154            self.record_nesting_error(depth);
155            Some(depth)
156        } else {
157            None
158        }
159    }
160
161    /// 退出一层嵌套(与 [`Self::enter_nesting`] 成对调用)。
162    pub fn leave_nesting(&self) {
163        self.depth.set(self.depth.get().saturating_sub(1));
164    }
165
166    /// 返回 `tokens[start_index..end_index]` 对应的原始 source text。
167    ///
168    /// 参数是 **token 索引**(不是 char/byte 索引)。
169    /// 返回 `None` 如果无 source tracking 或 index 越界。
170    pub fn source_slice(&self, start_index: usize, end_index: usize) -> Option<&str> {
171        let source = self.source.as_ref()?;
172        if end_index == 0 || start_index >= end_index {
173            return Some("");
174        }
175        let start = self.token_spans.get(start_index)?.start;
176        let end = self.token_spans.get(end_index - 1)?.end;
177        source.get(start..end)
178    }
179
180    /// §5.3 L1769-1773: The item of `tokens` at `index`. If
181    /// out-of-bounds, return `Token::Eof`.
182    pub fn next_token(&self) -> Token {
183        self.tokens.get(self.index).cloned().unwrap_or(Token::Eof)
184    }
185
186    /// §5.3 L1775-1777: A token stream is empty if the next token is
187    /// `<EOF-token>`.
188    pub fn is_empty(&self) -> bool {
189        matches!(self.next_token(), Token::Eof)
190    }
191
192    /// §5.3 L1779-1782: Let `token` be the next token. Increment
193    /// `index`, then return `token`.
194    pub fn consume_token(&mut self) -> Token {
195        let token = self.next_token();
196        if !matches!(token, Token::Eof) {
197            self.index += 1;
198        }
199        token
200    }
201
202    /// §5.3 L1784-1786: If not empty, increment `index`.
203    pub fn discard_token(&mut self) {
204        if !self.is_empty() {
205            self.index += 1;
206        }
207    }
208
209    /// §5.3 L1788-1789: Append `index` to `marked_indexes`.
210    pub fn mark(&mut self) {
211        self.marked_indexes.push(self.index);
212    }
213
214    /// §5.3 L1791-1793: Pop from `marked_indexes` and set `index` to
215    /// the popped value. No-op if stack is empty (defensive).
216    pub fn restore_mark(&mut self) {
217        if let Some(idx) = self.marked_indexes.pop() {
218            self.index = idx;
219        }
220    }
221
222    /// §5.3 L1795-1797: Pop from `marked_indexes` and discard.
223    pub fn discard_mark(&mut self) {
224        let _ = self.marked_indexes.pop();
225    }
226
227    /// §5.3 L1799-1801: While the next token is a
228    /// `<whitespace-token>`, discard a token.
229    pub fn discard_whitespace(&mut self) {
230        while matches!(self.next_token(), Token::Whitespace) {
231            self.discard_token();
232        }
233    }
234}