Skip to main content

parsec_css/values/
grammar.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! The value definition syntax, CSS Values and Units Level 4 §2: the
5//! language every property's grammar is written in, `<length> | auto`
6//! and the like, parsed into a tree the matcher walks.
7
8use std::sync::OnceLock;
9
10/// A reference to a type, `<name>` or `<name [min,max]>`, with what it
11/// names looked up once, the first time it's matched.
12#[derive(Debug)]
13pub struct TypeRef {
14    pub name: Box<str>,
15    pub range: Option<(f64, f64)>,
16    pub(crate) target: OnceLock<super::matcher::Target>,
17    /// What its value can start with, for skipping it when it can't.
18    pub(crate) first: OnceLock<super::matcher::First>,
19}
20
21impl Clone for TypeRef {
22    fn clone(&self) -> TypeRef {
23        TypeRef {
24            name: self.name.clone(),
25            range: self.range,
26            target: OnceLock::new(),
27            first: OnceLock::new(),
28        }
29    }
30}
31
32impl PartialEq for TypeRef {
33    fn eq(&self, other: &TypeRef) -> bool {
34        self.name == other.name && self.range == other.range
35    }
36}
37
38/// A reference to a property's grammar, `<'name'>`, looked up once.
39#[derive(Debug)]
40pub struct PropertyRef {
41    pub name: Box<str>,
42    #[allow(clippy::type_complexity)]
43    pub(crate) target: OnceLock<Option<(&'static super::PropertyData, &'static Grammar)>>,
44    pub(crate) first: OnceLock<super::matcher::First>,
45}
46
47impl Clone for PropertyRef {
48    fn clone(&self) -> PropertyRef {
49        PropertyRef {
50            name: self.name.clone(),
51            target: OnceLock::new(),
52            first: OnceLock::new(),
53        }
54    }
55}
56
57impl PartialEq for PropertyRef {
58    fn eq(&self, other: &PropertyRef) -> bool {
59        self.name == other.name
60    }
61}
62
63/// A grammar, parsed.
64#[derive(Clone, Debug, PartialEq)]
65pub enum Grammar {
66    /// A keyword, in lowercase, matched ignoring ASCII case.
67    Keyword(Box<str>),
68    /// A literal token: `,`, `/`, `+`, `:` and the like.
69    Literal(char),
70    /// `<name>` or `<name [min,max]>`.
71    Type(TypeRef),
72    /// `<'name'>`: whatever that property's value can be.
73    Property(PropertyRef),
74    /// `name( … )`.
75    Function(Box<str>, Box<Grammar>),
76    /// `[ … ]` written as a literal block in the value: `'[' … ']'`.
77    SquareBlock(Box<Grammar>),
78    /// `( … )`: a parenthesized block in the value.
79    ParenBlock(Box<Grammar>),
80    /// Juxtaposition: all, in order.
81    Sequence(Vec<Grammar>),
82    /// `&&`: all, in any order.
83    All(Vec<Grammar>),
84    /// `||`: one or more, in any order.
85    Any(Vec<Grammar>),
86    /// `|`: exactly one.
87    One(Vec<Grammar>),
88    /// A multiplier: `*`, `+`, `?`, `{a,b}`, and `#` when `commas`.
89    Repeat {
90        item: Box<Grammar>,
91        min: u32,
92        max: u32,
93        commas: bool,
94    },
95    /// `[ … ]!`: the group must match at least one value.
96    NonEmpty(Box<Grammar>),
97    /// Matches nothing: for a definition that's prose, not grammar.
98    Never,
99}
100
101#[derive(Clone, Debug, PartialEq)]
102enum Tok {
103    Word(String),
104    Type(String, Option<(f64, f64)>),
105    Property(String),
106    FunctionType(String),
107    Function(String),
108    Literal(char),
109    Open,
110    Close,
111    OpenParen,
112    CloseParen,
113    Bar,
114    Bars,
115    Ands,
116    Star,
117    Plus,
118    Question,
119    Hash,
120    Bang,
121    Range(u32, u32),
122}
123
124fn bound(s: &str) -> Option<f64> {
125    match s.trim() {
126        "∞" | "+∞" | "infinity" => Some(f64::INFINITY),
127        "-∞" | "−∞" | "-infinity" => Some(f64::NEG_INFINITY),
128        s => {
129            // `0px`, `1deg`: the number is what bounds.
130            let end = s
131                .find(|c: char| !(c.is_ascii_digit() || matches!(c, '.' | '-' | '+' | 'e')))
132                .unwrap_or(s.len());
133            s[..end].parse().ok()
134        }
135    }
136}
137
138fn tokenize(src: &str) -> Option<Vec<Tok>> {
139    let b: Vec<char> = src.chars().collect();
140    let mut out = Vec::new();
141    let mut i = 0;
142    while i < b.len() {
143        let c = b[i];
144        match c {
145            _ if c.is_whitespace() => i += 1,
146            '<' => {
147                let end = (i..b.len()).find(|&j| b[j] == '>')?;
148                let inner: String = b[i + 1..end].iter().collect();
149                let inner = inner.trim();
150                if let Some(p) = inner.strip_prefix('\'') {
151                    out.push(Tok::Property(p.trim_end_matches('\'').to_string()));
152                } else if let Some(f) = inner.strip_suffix("()") {
153                    out.push(Tok::FunctionType(f.to_string()));
154                } else if let Some((name, range)) = inner.split_once('[') {
155                    let range = range.trim_end_matches(']');
156                    // A numeric range, or a generic type's argument, which
157                    // this doesn't model: `<boolean-expr[ <if-test> ]>`.
158                    let bounds = range
159                        .split_once(',')
160                        .and_then(|(lo, hi)| Some((bound(lo)?, bound(hi)?)));
161                    out.push(Tok::Type(name.trim().to_string(), bounds));
162                } else {
163                    out.push(Tok::Type(inner.to_string(), None));
164                }
165                i = end + 1;
166            }
167            '\'' => {
168                let end = (i + 1..b.len()).find(|&j| b[j] == '\'')?;
169                let lit: String = b[i + 1..end].iter().collect();
170                let mut chars = lit.chars();
171                match (chars.next(), chars.next()) {
172                    (Some('['), None) => out.push(Tok::Literal('[')),
173                    (Some(']'), None) => out.push(Tok::Literal(']')),
174                    (Some(c), None) => out.push(Tok::Literal(c)),
175                    // A quoted word is a keyword that looks like syntax.
176                    _ => out.push(Tok::Word(lit)),
177                }
178                i = end + 1;
179            }
180            '[' => {
181                out.push(Tok::Open);
182                i += 1;
183            }
184            ']' => {
185                out.push(Tok::Close);
186                i += 1;
187            }
188            '(' => {
189                out.push(Tok::OpenParen);
190                i += 1;
191            }
192            ')' => {
193                out.push(Tok::CloseParen);
194                i += 1;
195            }
196            '|' if b.get(i + 1) == Some(&'|') => {
197                out.push(Tok::Bars);
198                i += 2;
199            }
200            '|' => {
201                out.push(Tok::Bar);
202                i += 1;
203            }
204            '&' if b.get(i + 1) == Some(&'&') => {
205                out.push(Tok::Ands);
206                i += 2;
207            }
208            '*' => {
209                out.push(Tok::Star);
210                i += 1;
211            }
212            '+' => {
213                out.push(Tok::Plus);
214                i += 1;
215            }
216            '?' => {
217                out.push(Tok::Question);
218                i += 1;
219            }
220            '#' => {
221                out.push(Tok::Hash);
222                i += 1;
223            }
224            '!' => {
225                out.push(Tok::Bang);
226                i += 1;
227            }
228            '{' => {
229                let end = (i..b.len()).find(|&j| b[j] == '}')?;
230                let inner: String = b[i + 1..end].iter().collect();
231                let num = |s: &str| s.trim().parse::<u32>().ok();
232                let range = match inner.split_once(',') {
233                    Some((lo, hi)) if hi.trim().is_empty() => num(lo).map(|lo| (lo, u32::MAX)),
234                    Some((lo, hi)) => num(lo).zip(num(hi)),
235                    None => num(&inner).map(|n| (n, n)),
236                };
237                match range {
238                    Some((lo, hi)) => {
239                        out.push(Tok::Range(lo, hi));
240                        i = end + 1;
241                    }
242                    // A literal `{`, as an at-rule's grammar has: never a
243                    // token in a value, so it matches nothing.
244                    None => {
245                        out.push(Tok::Literal('{'));
246                        i += 1;
247                    }
248                }
249            }
250            '}' => {
251                out.push(Tok::Literal('}'));
252                i += 1;
253            }
254            ',' | '/' | ':' | ';' | '=' => {
255                out.push(Tok::Literal(c));
256                i += 1;
257            }
258            _ => {
259                let start = i;
260                while i < b.len()
261                    && (b[i].is_alphanumeric() || matches!(b[i], '-' | '_' | '@' | '.' | '%'))
262                {
263                    i += 1;
264                }
265                if i == start {
266                    return None;
267                }
268                let word: String = b[start..i].iter().collect();
269                if b.get(i) == Some(&'(') {
270                    out.push(Tok::Function(word.to_ascii_lowercase()));
271                    i += 1;
272                } else {
273                    out.push(Tok::Word(word));
274                }
275            }
276        }
277    }
278    Some(out)
279}
280
281struct P {
282    toks: Vec<Tok>,
283    i: usize,
284}
285
286impl P {
287    fn peek(&self) -> Option<&Tok> {
288        self.toks.get(self.i)
289    }
290
291    /// `|` binds loosest, then `||`, then `&&`, then juxtaposition.
292    fn one(&mut self) -> Option<Grammar> {
293        let mut alts = vec![self.any()?];
294        while self.peek() == Some(&Tok::Bar) {
295            self.i += 1;
296            alts.push(self.any()?);
297        }
298        if alts.len() == 1 {
299            return alts.pop();
300        }
301        // Values 4 §6.2: where a `<number>` would do, a unitless zero is
302        // one rather than a `<length>`, so numbers are tried first.
303        let numeric = |g: &Grammar, name: &str| matches!(g, Grammar::Type(t) if &*t.name == name);
304        if let (Some(n), Some(l)) = (
305            alts.iter().position(|a| numeric(a, "number")),
306            alts.iter().position(|a| numeric(a, "length")),
307        ) && n > l
308        {
309            let number = alts.remove(n);
310            alts.insert(l, number);
311        }
312        Some(Grammar::One(alts))
313    }
314
315    fn any(&mut self) -> Option<Grammar> {
316        let mut alts = vec![self.all()?];
317        while self.peek() == Some(&Tok::Bars) {
318            self.i += 1;
319            alts.push(self.all()?);
320        }
321        Some(if alts.len() == 1 {
322            alts.pop().unwrap()
323        } else {
324            Grammar::Any(alts)
325        })
326    }
327
328    fn all(&mut self) -> Option<Grammar> {
329        let mut alts = vec![self.sequence()?];
330        while self.peek() == Some(&Tok::Ands) {
331            self.i += 1;
332            alts.push(self.sequence()?);
333        }
334        Some(if alts.len() == 1 {
335            alts.pop().unwrap()
336        } else {
337            Grammar::All(alts)
338        })
339    }
340
341    fn sequence(&mut self) -> Option<Grammar> {
342        let mut items = Vec::new();
343        while let Some(t) = self.peek() {
344            if matches!(
345                t,
346                Tok::Bar | Tok::Bars | Tok::Ands | Tok::Close | Tok::CloseParen | Tok::Literal(']')
347            ) {
348                break;
349            }
350            items.push(self.multiplied()?);
351        }
352        match items.len() {
353            0 => None,
354            1 => items.pop(),
355            _ => Some(Grammar::Sequence(items)),
356        }
357    }
358
359    fn multiplied(&mut self) -> Option<Grammar> {
360        let mut g = self.term()?;
361        loop {
362            let (min, max, commas) = match self.peek() {
363                Some(Tok::Star) => (0, u32::MAX, false),
364                Some(Tok::Plus) => (1, u32::MAX, false),
365                Some(Tok::Question) => (0, 1, false),
366                Some(Tok::Range(a, b)) => (*a, *b, false),
367                Some(Tok::Hash) => {
368                    self.i += 1;
369                    if let Some(Tok::Range(a, b)) = self.peek() {
370                        let (a, b) = (*a, *b);
371                        self.i += 1;
372                        g = Grammar::Repeat {
373                            item: Box::new(g),
374                            min: a,
375                            max: b,
376                            commas: true,
377                        };
378                    } else {
379                        g = Grammar::Repeat {
380                            item: Box::new(g),
381                            min: 1,
382                            max: u32::MAX,
383                            commas: true,
384                        };
385                    }
386                    continue;
387                }
388                Some(Tok::Bang) => {
389                    self.i += 1;
390                    g = Grammar::NonEmpty(Box::new(g));
391                    continue;
392                }
393                _ => return Some(g),
394            };
395            self.i += 1;
396            g = Grammar::Repeat {
397                item: Box::new(g),
398                min,
399                max,
400                commas,
401            };
402        }
403    }
404
405    fn term(&mut self) -> Option<Grammar> {
406        let t = self.peek()?.clone();
407        self.i += 1;
408        Some(match t {
409            Tok::Word(w) => Grammar::Keyword(w.to_ascii_lowercase().into()),
410            Tok::Literal('[') => {
411                // `'[' <custom-ident>* ']'`: a square block in the value.
412                let inner = self.one()?;
413                if self.peek() != Some(&Tok::Literal(']')) {
414                    return None;
415                }
416                self.i += 1;
417                Grammar::SquareBlock(Box::new(inner))
418            }
419            Tok::Literal(c) => Grammar::Literal(c),
420            Tok::Type(name, range) => Grammar::Type(TypeRef {
421                name: name.into(),
422                range,
423                target: OnceLock::new(),
424                first: OnceLock::new(),
425            }),
426            Tok::Property(p) => Grammar::Property(PropertyRef {
427                name: p.into(),
428                target: OnceLock::new(),
429                first: OnceLock::new(),
430            }),
431            Tok::FunctionType(f) => Grammar::Type(TypeRef {
432                name: format!("{f}()").into(),
433                range: None,
434                target: OnceLock::new(),
435                first: OnceLock::new(),
436            }),
437            Tok::Function(name) => {
438                let inner = if self.peek() == Some(&Tok::CloseParen) {
439                    Grammar::Sequence(Vec::new())
440                } else {
441                    self.one()?
442                };
443                if self.peek() != Some(&Tok::CloseParen) {
444                    return None;
445                }
446                self.i += 1;
447                Grammar::Function(name.into(), Box::new(inner))
448            }
449            Tok::OpenParen => {
450                let inner = self.one()?;
451                if self.peek() != Some(&Tok::CloseParen) {
452                    return None;
453                }
454                self.i += 1;
455                Grammar::ParenBlock(Box::new(inner))
456            }
457            Tok::Open => {
458                let inner = self.one()?;
459                if self.peek() != Some(&Tok::Close) {
460                    return None;
461                }
462                self.i += 1;
463                inner
464            }
465            _ => return None,
466        })
467    }
468}
469
470impl Grammar {
471    /// Parses a grammar written in the value definition syntax, or `None`
472    /// if it isn't one.
473    ///
474    /// ```
475    /// use parsec_css::values::Grammar;
476    ///
477    /// let g = Grammar::parse("<length [0,∞]>{1,4} | auto").unwrap();
478    /// assert!(matches!(g, Grammar::One(alts) if alts.len() == 2));
479    /// ```
480    pub fn parse(src: &str) -> Option<Grammar> {
481        let toks = tokenize(src)?;
482        let mut p = P { toks, i: 0 };
483        let g = p.one()?;
484        (p.i == p.toks.len()).then_some(g)
485    }
486}
487
488#[cfg(test)]
489mod tests {
490    use super::*;
491
492    #[test]
493    fn parses_every_grammar_in_the_table() {
494        let mut bad = Vec::new();
495        for p in super::super::generated::PROPERTIES {
496            if let Some(s) = p.syntax
497                && Grammar::parse(s).is_none()
498            {
499                bad.push(format!("{}: {s}", p.name));
500            }
501        }
502        // Written in tokens rather than values (`<function-token> … )`), or
503        // generic (`<boolean-expr[ <if-test> ]>`): grammars for preludes
504        // and conditions, which no property's value uses.
505        let token_level = ["general-enclosed", "if-condition", "pseudo-class-selector"];
506        for (name, s) in super::super::generated::TYPES
507            .iter()
508            .chain(super::super::generated::FUNCTIONS)
509        {
510            if Grammar::parse(s).is_none() && !token_level.contains(name) {
511                bad.push(format!("<{name}>: {s}"));
512            }
513        }
514        assert!(
515            bad.is_empty(),
516            "{} didn't parse:\n{}",
517            bad.len(),
518            bad.join("\n")
519        );
520    }
521
522    #[test]
523    fn precedence_and_multipliers() {
524        let g = Grammar::parse("a b | c && d || e").unwrap();
525        let Grammar::One(alts) = g else { panic!() };
526        assert!(matches!(&alts[0], Grammar::Sequence(_)));
527        assert!(matches!(&alts[1], Grammar::Any(_)));
528        let g = Grammar::parse("<length>#{2,3}").unwrap();
529        assert!(matches!(
530            g,
531            Grammar::Repeat {
532                min: 2,
533                max: 3,
534                commas: true,
535                ..
536            }
537        ));
538    }
539}