Skip to main content

muskitty_css_parser/
algorithms.rs

1//! §5.5 Parser Algorithms.
2//!
3//! Implementation of the 11 algorithms defined in CSS Syntax Module
4//! Level 3 §5.5. This module covers:
5//! - CP-3 (lower-level algorithms): §5.5.7-§5.5.11.
6//! - CP-4 (declaration algorithms): §5.5.6.
7//! - CP-5 (stylesheet/rule/block algorithms): §5.5.1-§5.5.5.
8
9use crate::token_stream::TokenStream;
10use crate::types::{
11    AtRule, BlockKind, ComponentValue, Declaration, Function, ParseError, QualifiedRule, Rule,
12    SimpleBlock,
13};
14use muskitty_css_tokenizer::Token;
15
16/// §5.5.8 (L2776-2796) Consume a component value.
17///
18/// Dispatch on the next token:
19/// - `{-token` / `[-token` / `(-token` → consume_a_simple_block
20/// - `function-token` → consume_a_function
21/// - anything else → consume and return the token as PreservedToken
22pub fn consume_a_component_value(input: &mut TokenStream) -> ComponentValue {
23    match input.next_token() {
24        Token::OpenBrace | Token::OpenBracket | Token::OpenParen => {
25            ComponentValue::SimpleBlock(consume_a_simple_block(input))
26        }
27        Token::Function(_) => ComponentValue::Function(consume_a_function(input)),
28        other => {
29            input.consume_token();
30            ComponentValue::PreservedToken(other)
31        }
32    }
33}
34
35/// §5.5.9 (L2799-2829) Consume a simple block.
36///
37/// Precondition: next token is `{-token` / `[-token` / `(-token`. The
38/// mirror variant becomes the ending token (e.g. `[` → `]`).
39/// Repeatedly consume component values until the ending token or EOF.
40pub fn consume_a_simple_block(input: &mut TokenStream) -> SimpleBlock {
41    let opening = input.next_token();
42    let kind = match opening {
43        Token::OpenBrace => BlockKind::Curly,
44        Token::OpenBracket => BlockKind::Square,
45        Token::OpenParen => BlockKind::Paren,
46        _ => unreachable!("consume_a_simple_block called on non-opening token"),
47    };
48    let ending = match kind {
49        BlockKind::Curly => Token::CloseBrace,
50        BlockKind::Square => Token::CloseBracket,
51        BlockKind::Paren => Token::CloseParen,
52    };
53    // §5.5.9 L2818: discard the opening token.
54    input.discard_token();
55
56    let mut block = SimpleBlock {
57        kind,
58        value: Vec::new(),
59    };
60    loop {
61        // §5.5.9 L2822-2825: EOF or ending token → discard, return block.
62        let next = input.next_token();
63        if matches!(next, Token::Eof) || next == ending {
64            input.discard_token();
65            return block;
66        }
67        // §5.5.9 L2827-2829: anything else → consume a component value
68        // and append.
69        block.value.push(consume_a_component_value(input));
70    }
71}
72
73/// §5.5.10 (L2832-2854) Consume a function.
74///
75/// Precondition: next token is a `function-token`. Consume the function
76/// token, then consume component values until `)-token` or EOF.
77pub fn consume_a_function(input: &mut TokenStream) -> Function {
78    let name = match input.consume_token() {
79        Token::Function(name) => name,
80        _ => unreachable!("consume_a_function called on non-function token"),
81    };
82    let mut function = Function {
83        name,
84        value: Vec::new(),
85    };
86    loop {
87        // §5.5.10 L2847-2850: EOF or `)-token` → discard, return function.
88        match input.next_token() {
89            Token::Eof | Token::CloseParen => {
90                input.discard_token();
91                return function;
92            }
93            // §5.5.10 L2852-2854: anything else → consume a component
94            // value and append.
95            _ => function.value.push(consume_a_component_value(input)),
96        }
97    }
98}
99
100/// §5.5.7 (L2745-2774) Consume a list of component values.
101///
102/// `stop_token`: optional token that ends the list (e.g. `;` for
103/// declarations). `nested`: when true, an unbalanced `}-token` ends
104/// the list without consuming; when false, `}-token` is a parse
105/// error and is consumed into the list.
106pub fn consume_a_list_of_component_values(
107    input: &mut TokenStream,
108    stop_token: Option<Token>,
109    nested: bool,
110) -> Vec<ComponentValue> {
111    let mut values = Vec::new();
112    loop {
113        let next = input.next_token();
114        // §5.5.7 L2757-2759: EOF → return values.
115        if matches!(next, Token::Eof) {
116            return values;
117        }
118        // §5.5.7 L2757-2759: stop_token → return values.
119        if stop_token.as_ref().is_some_and(|s| *s == next) {
120            return values;
121        }
122        match next {
123            Token::CloseBrace => {
124                if nested {
125                    // §5.5.7 L2761-2764: nested → return values without
126                    // consuming the `}-token (caller handles it).
127                    return values;
128                }
129                // §5.5.7 L2766-2769: parse error. Consume and append.
130                input.consume_token();
131                values.push(ComponentValue::PreservedToken(next));
132            }
133            // §5.5.7 L2771-2773: anything else → consume a component
134            // value and append.
135            _ => values.push(consume_a_component_value(input)),
136        }
137    }
138}
139
140/// §5.5.11 (L2857-2872) Consume the value of a
141/// `@font-face/unicode-range` descriptor.
142///
143/// Tokenize `input_string` with `unicode_ranges_allowed=true`, then
144/// consume a list of component values from the resulting stream.
145///
146/// Per §5.5.11 L2869-2871 note: "The existence of this algorithm is
147/// due to a design mistake in early CSS. It should never be
148/// reproduced."
149pub fn consume_a_unicode_range_value(input_string: &str) -> Vec<ComponentValue> {
150    use muskitty_css_tokenizer::{CssTokenizer, Tokenizer};
151    let mut tz = CssTokenizer::new(input_string);
152    tz.set_unicode_ranges_allowed(true);
153    let mut tokens: Vec<Token> = Vec::new();
154    while let Some(token) = tz.next_token() {
155        let is_eof = matches!(token, Token::Eof);
156        tokens.push(token);
157        if is_eof {
158            break;
159        }
160    }
161    let mut stream = TokenStream::new(tokens);
162    consume_a_list_of_component_values(&mut stream, None, false)
163}
164
165// ─── §5.5.6 Declaration algorithms ───────────────────────────────────
166
167/// §5.5.6 (L2639-2717) Consume a declaration.
168///
169/// `nested`: when true, an unbalanced `}-token` returns `None` without
170/// consuming (caller will handle the closing brace); when false, it
171/// is consumed as part of the declaration's value.
172///
173/// # Algorithm steps
174///
175/// 1. If next token is ident, consume it as the declaration name.
176///    Otherwise, consume remnants of a bad declaration, return `None`.
177/// 2. Discard whitespace.
178/// 3. If next token is `:`, discard it. Otherwise, bad declaration,
179///    return `None`.
180/// 4. Discard whitespace.
181/// 5. Consume a list of component values with `;` as stop token.
182/// 6. If last two non-whitespace values are `!` + `important` (ASCII
183///    case-insensitive), remove them and set `important` flag.
184/// 7. Strip trailing whitespace tokens.
185/// 8. Custom property (`--foo`): set `original_text` to the source text
186///    spanning the value tokens. Otherwise, if value contains a top-level
187///    {}-block AND any other non-ws value, return `None` (only the whole
188///    value may be a {}-block for non-custom properties).
189/// 9. (§5.5.6 L2707-2712: `unicode-range` descriptor handling
190///    deferred — requires source-text tracking.)
191pub fn consume_a_declaration(input: &mut TokenStream, nested: bool) -> Option<Declaration> {
192    // Step 1 (§5.5.6 L2650-2659): ident-token as declaration name.
193    let name = match input.next_token() {
194        Token::Ident(name) => {
195            input.consume_token();
196            name
197        }
198        _ => {
199            consume_the_remnants_of_a_bad_declaration(input, nested);
200            return None;
201        }
202    };
203
204    // Step 2 (§5.5.6 L2661-2662): discard whitespace.
205    input.discard_whitespace();
206
207    // Step 3 (§5.5.6 L2664-2671): colon.
208    match input.next_token() {
209        Token::Colon => input.discard_token(),
210        _ => {
211            consume_the_remnants_of_a_bad_declaration(input, nested);
212            return None;
213        }
214    }
215
216    // Step 4 (§5.5.6 L2673-2674): discard whitespace.
217    input.discard_whitespace();
218
219    // 记录 value 消费前的 token index,供 §5.5.6 original_text 使用。
220    let value_start_index = input.index;
221
222    // Step 5 (§5.5.6 L2676-2680): consume value until `;`.
223    let mut value = consume_a_list_of_component_values(input, Some(Token::Semicolon), nested);
224
225    // value_end_index 指向 `;` 或 EOF(consume_a_list_of_component_values
226    // 消费到 stop token 前停止,不消费 stop token 本身)。
227    let value_end_index = input.index;
228
229    // Step 6 (§5.5.6 L2682-2687): strip !important from the tail.
230    let important = strip_important(&mut value);
231
232    // Step 7 (§5.5.6 L2689-2691): strip trailing whitespace.
233    while matches!(
234        value.last(),
235        Some(ComponentValue::PreservedToken(Token::Whitespace))
236    ) {
237        value.pop();
238    }
239
240    let mut decl = Declaration {
241        name,
242        value,
243        important,
244        original_text: None,
245    };
246
247    // Step 8 (§5.5.6 L2693-2705): custom property original_text +
248    // top-level {}-block validity check.
249    if is_custom_property_name(&decl.name) {
250        // §5.5.6 L2693-2698: set original_text to the source text
251        // spanning the value tokens (colon 后、semicolon/EOF 前)。
252        decl.original_text = input
253            .source_slice(value_start_index, value_end_index)
254            .map(|s| s.to_string());
255    } else {
256        // §5.5.6 L2700-2705: if value contains a top-level {}-block
257        // AND any other non-whitespace value, return nothing.
258        if has_top_level_curly_block_with_other_values(&decl.value) {
259            return None;
260        }
261    }
262
263    // §5.5.6 L2707-2712: `unicode-range` descriptor handling deferred
264    // (requires source-text tracking for re-tokenization).
265
266    // §5.5.6 L2714-2717: if the declaration is valid, return it;
267    // otherwise return nothing. We treat "valid" as "we successfully
268    // parsed a name + colon + value", which is the syntactic validity.
269    // Grammar-level validity is left to higher-level callers (CSSOM).
270    Some(decl)
271}
272
273/// §5.5.6 (L2721-2741) Consume the remnants of a bad declaration.
274///
275/// Repeatedly process input:
276/// - EOF or `;` → discard, return.
277/// - `}-token`: if `nested`, return without consuming; else discard.
278/// - anything else → consume a component value (discard result).
279pub fn consume_the_remnants_of_a_bad_declaration(input: &mut TokenStream, nested: bool) {
280    loop {
281        match input.next_token() {
282            Token::Eof | Token::Semicolon => {
283                input.discard_token();
284                return;
285            }
286            Token::CloseBrace => {
287                if nested {
288                    return;
289                }
290                input.discard_token();
291            }
292            _ => {
293                // Discard the consumed component value.
294                let _ = consume_a_component_value(input);
295            }
296        }
297    }
298}
299
300/// §5.5.6 step 6 (L2682-2687): If the last two non-whitespace values are
301/// a `!` delim token followed by an `important` ident (ASCII
302/// case-insensitive), remove them (and any trailing whitespace
303/// between/after) and return `true`. Otherwise return `false`.
304///
305/// This does NOT strip trailing whitespace after the `!important` —
306/// that is the caller's responsibility (step 7).
307fn strip_important(value: &mut Vec<ComponentValue>) -> bool {
308    // Find the index just past the last non-whitespace value.
309    let mut end = value.len();
310    while end > 0
311        && matches!(
312            value[end - 1],
313            ComponentValue::PreservedToken(Token::Whitespace)
314        )
315    {
316        end -= 1;
317    }
318    if end < 2 {
319        return false;
320    }
321    let last = &value[end - 1];
322    let prev = &value[end - 2];
323    let is_important_ident = |v: &ComponentValue| match v {
324        ComponentValue::PreservedToken(Token::Ident(s)) => s.eq_ignore_ascii_case("important"),
325        _ => false,
326    };
327    let is_bang_delim =
328        |v: &ComponentValue| matches!(v, ComponentValue::PreservedToken(Token::Delim('!')));
329    if is_bang_delim(prev) && is_important_ident(last) {
330        // Truncate to `end - 2`, removing the `!important` (and any
331        // trailing whitespace after it).
332        value.truncate(end - 2);
333        return true;
334    }
335    false
336}
337
338/// §5.5.6 L2693: A "custom property name string" is an ident-token
339/// whose value starts with `--` (two hyphens).
340fn is_custom_property_name(name: &str) -> bool {
341    name.starts_with("--")
342}
343
344/// §5.5.6 L2700-2705: A declaration value contains a top-level
345/// {}-block AND any other non-whitespace value. (Only the whole
346/// value may be a {}-block for non-custom properties.)
347fn has_top_level_curly_block_with_other_values(value: &[ComponentValue]) -> bool {
348    let mut has_curly_block = false;
349    let mut has_other = false;
350    for v in value {
351        match v {
352            ComponentValue::SimpleBlock(SimpleBlock {
353                kind: BlockKind::Curly,
354                ..
355            }) => {
356                has_curly_block = true;
357            }
358            ComponentValue::PreservedToken(Token::Whitespace) => {}
359            _ => {
360                has_other = true;
361            }
362        }
363    }
364    has_curly_block && has_other
365}
366
367// ─── §5.5.1-§5.5.5 Stylesheet/rule/block algorithms ──────────────────
368
369/// §5.5.1 (L2223-2279) Consume a stylesheet's contents.
370///
371/// Repeatedly process input:
372/// - whitespace / CDO / CDC → discard.
373/// - EOF → return rules.
374/// - at-keyword → consume_an_at_rule; if `Some`, append.
375/// - else → consume_a_qualified_rule; if `Some(rule)`, append.
376pub fn consume_a_stylesheets_contents(input: &mut TokenStream) -> Vec<Rule> {
377    let mut rules = Vec::new();
378    loop {
379        match input.next_token() {
380            Token::Whitespace | Token::Cdo | Token::Cdc => {
381                input.discard_token();
382            }
383            Token::Eof => return rules,
384            Token::AtKeyword(_) => {
385                if let Some(rule) = consume_an_at_rule(input, false) {
386                    rules.push(Rule::AtRule(rule));
387                }
388            }
389            _ => {
390                if let Ok(Some(rule)) = consume_a_qualified_rule(input, None, false) {
391                    rules.push(Rule::QualifiedRule(rule));
392                }
393            }
394        }
395    }
396}
397
398/// §5.5.2 (L2281-2337) Consume an at-rule.
399///
400/// `nested`: when true, an unbalanced `}-token` returns the rule
401/// without consuming (caller will close the block); when false,
402/// `}-token` is part of the prelude.
403pub fn consume_an_at_rule(input: &mut TokenStream, nested: bool) -> Option<AtRule> {
404    let name = match input.consume_token() {
405        Token::AtKeyword(name) => name,
406        _ => unreachable!("consume_an_at_rule called on non-at-keyword"),
407    };
408    let mut rule = AtRule {
409        name,
410        prelude: Vec::new(),
411        declarations: None,
412        child_rules: None,
413    };
414    loop {
415        match input.next_token() {
416            Token::Semicolon | Token::Eof => {
417                input.discard_token();
418                return Some(rule);
419            }
420            Token::CloseBrace => {
421                if nested {
422                    // §5.5.2 L2307-2310: nested → return rule (caller
423                    // handles the closing brace).
424                    return Some(rule);
425                }
426                // §5.5.2 L2313-2316: non-nested → consume to prelude
427                // (parse error, but tolerated).
428                let t = input.consume_token();
429                rule.prelude.push(ComponentValue::PreservedToken(t));
430            }
431            Token::OpenBrace => {
432                // §5.5.2 L2317-2331: consume_a_block → split into
433                // declarations + child rules.
434                let block = consume_a_block(input);
435                let (decls, rules) = split_block_contents(block);
436                rule.declarations = Some(decls);
437                rule.child_rules = Some(rules);
438                return Some(rule);
439            }
440            _ => {
441                // §5.5.2 L2333-2336: anything else → consume a
442                // component value, append to prelude.
443                rule.prelude.push(consume_a_component_value(input));
444            }
445        }
446    }
447}
448
449/// §5.5.3 (L2340-2466) Consume a qualified rule.
450///
451/// `stop_token`: optional token that aborts (returns `Ok(None)`).
452/// `nested`: passed down to consume_a_block's contents (controls
453/// `}-token` handling in nested contexts).
454///
455/// # Return values
456///
457/// - `Ok(Some(rule))` — rule successfully consumed.
458/// - `Ok(None)` — "return nothing" (e.g. EOF or stop_token).
459/// - `Err(ParseError)` — "invalid rule error" (e.g. custom-property-in-prelude
460///   at top level after consuming the block).
461pub fn consume_a_qualified_rule(
462    input: &mut TokenStream,
463    stop_token: Option<Token>,
464    nested: bool,
465) -> Result<Option<QualifiedRule>, ParseError> {
466    let mut rule = QualifiedRule {
467        prelude: Vec::new(),
468        declarations: Vec::new(),
469        child_rules: Vec::new(),
470    };
471    loop {
472        let next = input.next_token();
473        // §5.5.3 L2355-2359: EOF or stop_token → parse error, return
474        // nothing.
475        if matches!(next, Token::Eof) {
476            return Ok(None);
477        }
478        if stop_token.as_ref().is_some_and(|s| *s == next) {
479            return Ok(None);
480        }
481        match next {
482            Token::CloseBrace => {
483                // §5.5.3 L2361-2368: parse error.
484                if nested {
485                    return Ok(None);
486                }
487                let t = input.consume_token();
488                rule.prelude.push(ComponentValue::PreservedToken(t));
489            }
490            Token::OpenBrace => {
491                // §5.5.3 L2370-2460.
492                // §5.5.3 L2372-2383: check if prelude looks like
493                // `--<ident> :` (custom-property-like). If so:
494                //   nested → consume remnants of bad declaration, return
495                //           nothing.
496                //   non-nested → consume a block, return invalid rule
497                //                error.
498                if looks_like_custom_property_in_prelude(&rule.prelude) {
499                    if nested {
500                        consume_the_remnants_of_a_bad_declaration(input, true);
501                        return Ok(None);
502                    } else {
503                        let _ = consume_a_block(input);
504                        return Err(ParseError::new(
505                            "qualified rule with custom property in prelude is invalid when not nested",
506                        ));
507                    }
508                }
509                let block = consume_a_block(input);
510                let (decls, rules) = split_block_contents(block);
511                rule.declarations = decls;
512                rule.child_rules = rules;
513                return Ok(Some(rule));
514            }
515            _ => {
516                // §5.5.3 L2462-2465: anything else → consume a
517                // component value, append to prelude.
518                rule.prelude.push(consume_a_component_value(input));
519            }
520        }
521    }
522}
523
524/// §5.5.4 (L2469-2484) Consume a block.
525///
526/// Precondition: next token is `{-token`. Discard it, consume block
527/// contents, discard `}-token (or EOF), return the contents.
528pub fn consume_a_block(input: &mut TokenStream) -> BlockContents {
529    debug_assert!(matches!(input.next_token(), Token::OpenBrace));
530    input.discard_token();
531    let contents = consume_a_blocks_contents(input);
532    // §5.5.4 L2481: discard the closing `}-token (or EOF if implicit).
533    input.discard_token();
534    contents
535}
536
537/// §5.5.5 (L2486-2636) Consume a block's contents.
538///
539/// Returns a list of rules and lists-of-declarations (modeled as
540/// [`BlockContents`] carrying `Vec<Declaration>` and `Vec<Rule>`).
541/// Algorithm:
542/// - whitespace / `;` → discard.
543/// - EOF / `}` → return.
544/// - at-keyword → flush decls into rules (as `Rule::Declarations`),
545///   then `consume_an_at_rule(nested=true)`.
546/// - else → mark; `consume_a_declaration(nested=true)`; if
547///   `Some(decl)`, append to decls and discard mark. Otherwise
548///   `restore_mark`, then `consume_a_qualified_rule(nested=true,
549///   stop=`;`)`; on `Ok(Some(rule))`, flush decls to rules, append
550///   rule; on `Err(())`, flush decls to rules; on `Ok(None)`, do
551///   nothing.
552pub fn consume_a_blocks_contents(input: &mut TokenStream) -> BlockContents {
553    let mut rules: Vec<Rule> = Vec::new();
554    let mut decls: Vec<Declaration> = Vec::new();
555    loop {
556        match input.next_token() {
557            Token::Whitespace | Token::Semicolon => {
558                input.discard_token();
559            }
560            Token::Eof | Token::CloseBrace => {
561                // §5.5.5 L2514-2517: end of block — flush decls.
562                if !decls.is_empty() {
563                    rules.push(Rule::Declarations(std::mem::take(&mut decls)));
564                }
565                return BlockContents { rules };
566            }
567            Token::AtKeyword(_) => {
568                // §5.5.5 L2519-2528: at-keyword flushes decls.
569                if !decls.is_empty() {
570                    rules.push(Rule::Declarations(std::mem::take(&mut decls)));
571                }
572                if let Some(at_rule) = consume_an_at_rule(input, true) {
573                    rules.push(Rule::AtRule(at_rule));
574                }
575            }
576            _ => {
577                // §5.5.5 L2530-2562: mark + declaration/rule ambiguity.
578                input.mark();
579                if let Some(decl) = consume_a_declaration(input, true) {
580                    decls.push(decl);
581                    input.discard_mark();
582                } else {
583                    input.restore_mark();
584                    match consume_a_qualified_rule(input, Some(Token::Semicolon), true) {
585                        Ok(Some(rule)) => {
586                            // §5.5.5 L2556-2561: rule returned.
587                            if !decls.is_empty() {
588                                rules.push(Rule::Declarations(std::mem::take(&mut decls)));
589                            }
590                            rules.push(Rule::QualifiedRule(rule));
591                        }
592                        Ok(None) => {
593                            // §5.5.5 L2546-2547: "If nothing was
594                            // returned, do nothing."
595                        }
596                        Err(_) => {
597                            // §5.5.5 L2549-2554: invalid rule error.
598                            if !decls.is_empty() {
599                                rules.push(Rule::Declarations(std::mem::take(&mut decls)));
600                            }
601                        }
602                    }
603                }
604            }
605        }
606    }
607}
608
609/// Result of `consume_a_block` / `consume_a_blocks_contents`. Combines
610/// a list of declarations (possibly empty) and a list of child rules.
611///
612/// Result of `consume_a_block` / `consume_a_blocks_contents`.
613///
614/// All declarations are already flushed into `rules` as
615/// `Rule::Declarations` variants per §5.5.5 L2514-2562.
616#[derive(Debug, Clone, Default)]
617pub struct BlockContents {
618    pub rules: Vec<Rule>,
619}
620
621/// Split block contents into the AtRule / QualifiedRule's expected shape.
622fn split_block_contents(block: BlockContents) -> (Vec<Declaration>, Vec<Rule>) {
623    (Vec::new(), block.rules)
624}
625
626/// §5.5.3 L2372-2383: Detect whether a qualified rule's prelude
627/// looks like `--<ident> :` (a custom property declaration
628/// masquerading as a rule). The first two non-whitespace tokens of
629/// the prelude must be:
630///   - Ident starting with `--`
631///   - Colon
632fn looks_like_custom_property_in_prelude(prelude: &[ComponentValue]) -> bool {
633    let mut iter = prelude
634        .iter()
635        .filter(|v| !matches!(v, ComponentValue::PreservedToken(Token::Whitespace)));
636    let first = iter.next();
637    let second = iter.next();
638    matches!(
639        (first, second),
640        (
641            Some(ComponentValue::PreservedToken(Token::Ident(name))),
642            Some(ComponentValue::PreservedToken(Token::Colon))
643        ) if name.starts_with("--")
644    )
645}