stix_pattern/
lexer.rs

1//! Lexer: converts a pattern string into a flat token stream.
2
3use crate::error::{ParseError, Result, Span};
4
5/// A lexed token: its kind plus the source span it was read from.
6#[derive(Debug, Clone, PartialEq)]
7pub struct Token {
8    /// What kind of token this is (and any literal payload).
9    pub kind: TokenKind,
10    /// The byte range in the source the token was read from.
11    pub span: Span,
12}
13
14/// The kind of a lexed token.
15#[derive(Debug, Clone, PartialEq)]
16pub enum TokenKind {
17    // Punctuation
18    /// `[`
19    LBracket,
20    /// `]`
21    RBracket,
22    /// `(`
23    LParen,
24    /// `)`
25    RParen,
26    /// `:`
27    Colon,
28    /// `.`
29    Dot,
30    /// `,`
31    Comma,
32    /// `*`
33    Star,
34    // Comparison operators
35    /// `=`
36    Equal,
37    /// `!=` or `<>`
38    NotEqual,
39    /// `<`
40    LessThan,
41    /// `<=`
42    LessThanOrEqual,
43    /// `>`
44    GreaterThan,
45    /// `>=`
46    GreaterThanOrEqual,
47    // Keywords
48    /// The `AND` keyword.
49    And,
50    /// The `OR` keyword.
51    Or,
52    /// The `NOT` keyword.
53    Not,
54    /// The `FOLLOWEDBY` keyword.
55    FollowedBy,
56    /// The `LIKE` keyword.
57    Like,
58    /// The `MATCHES` keyword.
59    Matches,
60    /// The `IN` keyword.
61    In,
62    /// The `ISSUBSET` keyword.
63    IsSubset,
64    /// The `ISSUPERSET` keyword.
65    IsSuperset,
66    /// The `EXISTS` keyword.
67    Exists,
68    /// The `WITHIN` keyword.
69    Within,
70    /// The `REPEATS` keyword.
71    Repeats,
72    /// The `SECONDS` keyword.
73    Seconds,
74    /// The `TIMES` keyword.
75    Times,
76    /// The `START` keyword.
77    Start,
78    /// The `STOP` keyword.
79    Stop,
80    // Literals & identifiers
81    /// A bare identifier (object type or property name).
82    Identifier(String),
83    /// A single-quoted string literal (unescaped contents).
84    String(String),
85    /// An integer literal.
86    Integer(i64),
87    /// A floating-point literal.
88    Float(f64),
89    /// A `true`/`false` literal.
90    Boolean(bool),
91    /// A `t'...'` timestamp literal (inner string).
92    Timestamp(String),
93    /// A `b'...'` base64 literal (inner string).
94    Binary(String),
95    /// An `h'...'` hex literal (inner string).
96    Hex(String),
97}
98
99/// Tokenize a STIX pattern string into a vector of tokens.
100pub fn tokenize(src: &str) -> Result<Vec<Token>> {
101    Lexer::new(src).run()
102}
103
104struct Lexer<'a> {
105    src: &'a [u8],
106    pos: usize,
107    tokens: Vec<Token>,
108}
109
110impl<'a> Lexer<'a> {
111    fn new(src: &'a str) -> Self {
112        Lexer {
113            src: src.as_bytes(),
114            pos: 0,
115            tokens: Vec::new(),
116        }
117    }
118
119    fn run(mut self) -> Result<Vec<Token>> {
120        while let Some(&c) = self.src.get(self.pos) {
121            match c {
122                b' ' | b'\t' | b'\r' | b'\n' => self.pos += 1,
123                b'[' => self.punct(TokenKind::LBracket),
124                b']' => self.punct(TokenKind::RBracket),
125                b'(' => self.punct(TokenKind::LParen),
126                b')' => self.punct(TokenKind::RParen),
127                b':' => self.punct(TokenKind::Colon),
128                b'.' if !self.peek_is_digit(1) => self.punct(TokenKind::Dot),
129                b',' => self.punct(TokenKind::Comma),
130                b'*' => self.punct(TokenKind::Star),
131                b'=' => self.punct(TokenKind::Equal),
132                b'!' => self.lex_bang()?,
133                b'<' => self.lex_lt(),
134                b'>' => self.lex_gt(),
135                b'\'' => self.lex_string()?,
136                b'-' | b'0'..=b'9' => self.lex_number()?,
137                _ if is_ident_start(c) => self.lex_word_or_typed_literal()?,
138                _ => {
139                    return Err(ParseError::new(
140                        format!("unexpected character '{}'", c as char),
141                        Span::new(self.pos, self.pos + 1),
142                    ))
143                }
144            }
145        }
146        Ok(self.tokens)
147    }
148
149    fn peek_is_digit(&self, ahead: usize) -> bool {
150        matches!(self.src.get(self.pos + ahead), Some(b'0'..=b'9'))
151    }
152
153    fn push(&mut self, kind: TokenKind, start: usize) {
154        self.tokens.push(Token {
155            kind,
156            span: Span::new(start, self.pos),
157        });
158    }
159
160    fn punct(&mut self, kind: TokenKind) {
161        let start = self.pos;
162        self.pos += 1;
163        self.push(kind, start);
164    }
165
166    fn lex_bang(&mut self) -> Result<()> {
167        let start = self.pos;
168        if self.src.get(self.pos + 1) == Some(&b'=') {
169            self.pos += 2;
170            self.push(TokenKind::NotEqual, start);
171            Ok(())
172        } else {
173            Err(ParseError::new(
174                "expected '=' after '!'",
175                Span::new(start, start + 1),
176            ))
177        }
178    }
179
180    fn lex_lt(&mut self) {
181        let start = self.pos;
182        if self.src.get(self.pos + 1) == Some(&b'=') {
183            self.pos += 2;
184            self.push(TokenKind::LessThanOrEqual, start);
185        } else if self.src.get(self.pos + 1) == Some(&b'>') {
186            self.pos += 2;
187            self.push(TokenKind::NotEqual, start);
188        } else {
189            self.pos += 1;
190            self.push(TokenKind::LessThan, start);
191        }
192    }
193
194    fn lex_gt(&mut self) {
195        let start = self.pos;
196        if self.src.get(self.pos + 1) == Some(&b'=') {
197            self.pos += 2;
198            self.push(TokenKind::GreaterThanOrEqual, start);
199        } else {
200            self.pos += 1;
201            self.push(TokenKind::GreaterThan, start);
202        }
203    }
204
205    /// Reads a single-quoted string body starting at the opening quote.
206    /// Returns the decoded contents and advances past the closing quote.
207    fn read_quoted(&mut self) -> Result<String> {
208        let start = self.pos;
209        debug_assert_eq!(self.src.get(self.pos), Some(&b'\''));
210        self.pos += 1; // opening quote
211                       // Collect raw bytes and decode once: the escape bytes `\` and `'` are
212                       // ASCII and never occur inside a multi-byte UTF-8 sequence, and the
213                       // input is a `&str`, so the collected bytes are always valid UTF-8.
214        let mut out: Vec<u8> = Vec::new();
215        loop {
216            match self.src.get(self.pos) {
217                None => {
218                    return Err(ParseError::new(
219                        "unterminated string literal",
220                        Span::new(start, self.pos),
221                    ))
222                }
223                Some(b'\\') => match self.src.get(self.pos + 1) {
224                    Some(b'\'') => {
225                        out.push(b'\'');
226                        self.pos += 2;
227                    }
228                    Some(b'\\') => {
229                        out.push(b'\\');
230                        self.pos += 2;
231                    }
232                    _ => {
233                        out.push(b'\\');
234                        self.pos += 1;
235                    }
236                },
237                Some(b'\'') => {
238                    self.pos += 1; // closing quote
239                    return String::from_utf8(out).map_err(|_| {
240                        ParseError::new(
241                            "invalid UTF-8 in string literal",
242                            Span::new(start, self.pos),
243                        )
244                    });
245                }
246                Some(&b) => {
247                    out.push(b);
248                    self.pos += 1;
249                }
250            }
251        }
252    }
253
254    fn lex_string(&mut self) -> Result<()> {
255        let start = self.pos;
256        let s = self.read_quoted()?;
257        self.push(TokenKind::String(s), start);
258        Ok(())
259    }
260
261    fn lex_number(&mut self) -> Result<()> {
262        let start = self.pos;
263        if self.src.get(self.pos) == Some(&b'-') {
264            self.pos += 1;
265        }
266        let mut is_float = false;
267        while let Some(&c) = self.src.get(self.pos) {
268            match c {
269                b'0'..=b'9' => self.pos += 1,
270                b'.' => {
271                    is_float = true;
272                    self.pos += 1;
273                }
274                _ => break,
275            }
276        }
277        let text = std::str::from_utf8(&self.src[start..self.pos]).unwrap();
278        if is_float {
279            let v: f64 = text.parse().map_err(|_| {
280                ParseError::new("invalid float literal", Span::new(start, self.pos))
281            })?;
282            if !v.is_finite() {
283                return Err(ParseError::new(
284                    "float literal out of range",
285                    Span::new(start, self.pos),
286                ));
287            }
288            self.push(TokenKind::Float(v), start);
289        } else {
290            let v: i64 = text.parse().map_err(|_| {
291                ParseError::new("invalid integer literal", Span::new(start, self.pos))
292            })?;
293            self.push(TokenKind::Integer(v), start);
294        }
295        Ok(())
296    }
297
298    /// Handles bare words (keywords, identifiers, booleans) AND the typed-literal
299    /// prefixes `t'...'`, `b'...'`, `h'...'`.
300    fn lex_word_or_typed_literal(&mut self) -> Result<()> {
301        let start = self.pos;
302        // Typed-literal prefix: a single letter t/b/h immediately followed by a quote.
303        if matches!(self.src.get(self.pos), Some(b't' | b'b' | b'h'))
304            && self.src.get(self.pos + 1) == Some(&b'\'')
305        {
306            let prefix = self.src[self.pos];
307            self.pos += 1; // consume prefix letter
308            let body = self.read_quoted()?;
309            let kind = match prefix {
310                b't' => TokenKind::Timestamp(body),
311                b'b' => TokenKind::Binary(body),
312                _ => TokenKind::Hex(body),
313            };
314            self.push(kind, start);
315            return Ok(());
316        }
317
318        while let Some(&c) = self.src.get(self.pos) {
319            if is_ident_continue(c) {
320                self.pos += 1;
321            } else {
322                break;
323            }
324        }
325        let word = std::str::from_utf8(&self.src[start..self.pos]).unwrap();
326        let kind = keyword(word).unwrap_or_else(|| TokenKind::Identifier(word.to_string()));
327        self.push(kind, start);
328        Ok(())
329    }
330}
331
332fn is_ident_start(c: u8) -> bool {
333    c.is_ascii_alphabetic() || c == b'_'
334}
335
336/// Identifier continuation allows hyphens so object types like `ipv4-addr` lex as one token.
337fn is_ident_continue(c: u8) -> bool {
338    c.is_ascii_alphanumeric() || c == b'_' || c == b'-'
339}
340
341/// Map a bare word to a keyword token (case-insensitive), or `None` if it is an identifier.
342fn keyword(word: &str) -> Option<TokenKind> {
343    match word.to_ascii_uppercase().as_str() {
344        "AND" => Some(TokenKind::And),
345        "OR" => Some(TokenKind::Or),
346        "NOT" => Some(TokenKind::Not),
347        "FOLLOWEDBY" => Some(TokenKind::FollowedBy),
348        "LIKE" => Some(TokenKind::Like),
349        "MATCHES" => Some(TokenKind::Matches),
350        "IN" => Some(TokenKind::In),
351        "ISSUBSET" => Some(TokenKind::IsSubset),
352        "ISSUPERSET" => Some(TokenKind::IsSuperset),
353        "EXISTS" => Some(TokenKind::Exists),
354        "WITHIN" => Some(TokenKind::Within),
355        "REPEATS" => Some(TokenKind::Repeats),
356        "SECONDS" => Some(TokenKind::Seconds),
357        "TIMES" => Some(TokenKind::Times),
358        "START" => Some(TokenKind::Start),
359        "STOP" => Some(TokenKind::Stop),
360        "TRUE" => Some(TokenKind::Boolean(true)),
361        "FALSE" => Some(TokenKind::Boolean(false)),
362        _ => None,
363    }
364}
365
366#[cfg(test)]
367mod tests {
368    use super::*;
369
370    fn kinds(src: &str) -> Vec<TokenKind> {
371        tokenize(src).unwrap().into_iter().map(|t| t.kind).collect()
372    }
373
374    #[test]
375    fn lexes_simple_comparison() {
376        let k = kinds("[ipv4-addr:value = '1.2.3.4']");
377        assert_eq!(
378            k,
379            vec![
380                TokenKind::LBracket,
381                TokenKind::Identifier("ipv4-addr".to_string()),
382                TokenKind::Colon,
383                TokenKind::Identifier("value".to_string()),
384                TokenKind::Equal,
385                TokenKind::String("1.2.3.4".to_string()),
386                TokenKind::RBracket,
387            ]
388        );
389    }
390
391    #[test]
392    fn lexes_keywords_case_insensitively() {
393        assert_eq!(kinds("AND and"), vec![TokenKind::And, TokenKind::And]);
394        assert_eq!(kinds("FOLLOWEDBY"), vec![TokenKind::FollowedBy]);
395    }
396
397    #[test]
398    fn lexes_operators() {
399        assert_eq!(
400            kinds("= != < <= > >="),
401            vec![
402                TokenKind::Equal,
403                TokenKind::NotEqual,
404                TokenKind::LessThan,
405                TokenKind::LessThanOrEqual,
406                TokenKind::GreaterThan,
407                TokenKind::GreaterThanOrEqual,
408            ]
409        );
410    }
411
412    #[test]
413    fn lexes_literals() {
414        assert_eq!(kinds("42"), vec![TokenKind::Integer(42)]);
415        assert_eq!(kinds("-7"), vec![TokenKind::Integer(-7)]);
416        assert_eq!(kinds("2.5"), vec![TokenKind::Float(2.5)]);
417        assert_eq!(
418            kinds("true false"),
419            vec![TokenKind::Boolean(true), TokenKind::Boolean(false)]
420        );
421        assert_eq!(
422            kinds("t'2014-01-13T07:03:17Z'"),
423            vec![TokenKind::Timestamp("2014-01-13T07:03:17Z".to_string())]
424        );
425        assert_eq!(
426            kinds("b'aGVsbG8='"),
427            vec![TokenKind::Binary("aGVsbG8=".to_string())]
428        );
429        assert_eq!(
430            kinds("h'1234abcd'"),
431            vec![TokenKind::Hex("1234abcd".to_string())]
432        );
433    }
434
435    #[test]
436    fn lexes_string_escapes() {
437        assert_eq!(kinds(r"'a\'b'"), vec![TokenKind::String("a'b".to_string())]);
438        assert_eq!(
439            kinds(r"'a\\b'"),
440            vec![TokenKind::String(r"a\b".to_string())]
441        );
442    }
443
444    #[test]
445    fn unterminated_string_errors() {
446        let err = tokenize("'oops").unwrap_err();
447        assert!(err.message.contains("unterminated"), "got: {}", err.message);
448    }
449
450    #[test]
451    fn tracks_spans() {
452        let toks = tokenize("[a:b]").unwrap();
453        assert_eq!(toks[0].span, crate::error::Span::new(0, 1)); // '['
454    }
455
456    #[test]
457    fn lexes_diamond_not_equal() {
458        assert_eq!(kinds("<>"), vec![TokenKind::NotEqual]);
459        assert_eq!(
460            kinds("< >"),
461            vec![TokenKind::LessThan, TokenKind::GreaterThan]
462        );
463        assert_eq!(kinds("<="), vec![TokenKind::LessThanOrEqual]);
464    }
465
466    #[test]
467    fn rejects_overflowing_float_literal() {
468        let src = format!("{}.0", "9".repeat(400));
469        let err = tokenize(&src).unwrap_err();
470        assert!(
471            err.to_string().contains("float literal out of range"),
472            "{err}"
473        );
474    }
475
476    #[test]
477    fn decodes_non_ascii_strings_as_utf8() {
478        assert_eq!(kinds("'café'"), vec![TokenKind::String("café".to_string())]);
479        assert_eq!(kinds("'a😀b'"), vec![TokenKind::String("a😀b".to_string())]);
480        assert_eq!(kinds(r"'é\'é'"), vec![TokenKind::String("é'é".to_string())]);
481        assert_eq!(
482            kinds(r"'日本\\語'"),
483            vec![TokenKind::String("日本\\語".to_string())]
484        );
485    }
486
487    #[test]
488    fn non_ascii_token_spans_are_byte_offsets() {
489        let t = tokenize("'café' =").unwrap();
490        assert_eq!(t[0].span, Span::new(0, 7));
491        assert_eq!(t[1].span, Span::new(8, 9));
492    }
493
494    #[test]
495    fn typed_literals_still_lex() {
496        assert_eq!(
497            kinds("t'2020-01-01T00:00:00Z'"),
498            vec![TokenKind::Timestamp("2020-01-01T00:00:00Z".to_string())]
499        );
500        assert_eq!(
501            kinds("b'aGk='"),
502            vec![TokenKind::Binary("aGk=".to_string())]
503        );
504        assert_eq!(kinds("h'00ff'"), vec![TokenKind::Hex("00ff".to_string())]);
505    }
506}
stix_pattern/lexer.rs

stix_pattern/
lexer.rs
