stix_pattern/
parser.rs

1//! Recursive-descent parser: tokens -> AST.
2
3use crate::ast::{
4    Comparison, ComparisonExpression, ComparisonOperand, ComparisonOperator, Literal, ObjectPath,
5    ObservationExpression, PathStep, Pattern, Qualifier,
6};
7use crate::error::{ParseError, Result, Span};
8use crate::lexer::{Token, TokenKind};
9
10pub(crate) struct Parser<'a> {
11    tokens: &'a [Token],
12    pos: usize,
13    /// Length of the source string, used to build EOF spans.
14    src_len: usize,
15}
16
17impl<'a> Parser<'a> {
18    pub(crate) fn new(tokens: &'a [Token], src: &'a str) -> Self {
19        Parser {
20            tokens,
21            pos: 0,
22            src_len: src.len(),
23        }
24    }
25
26    // --- cursor helpers ---
27
28    fn peek(&self) -> Option<&TokenKind> {
29        self.tokens.get(self.pos).map(|t| &t.kind)
30    }
31
32    fn current_span(&self) -> Span {
33        match self.tokens.get(self.pos) {
34            Some(t) => t.span,
35            None => Span::new(self.src_len, self.src_len),
36        }
37    }
38
39    fn advance(&mut self) -> Option<&Token> {
40        let tok = self.tokens.get(self.pos);
41        if tok.is_some() {
42            self.pos += 1;
43        }
44        tok
45    }
46
47    fn at_end(&self) -> bool {
48        self.pos >= self.tokens.len()
49    }
50
51    /// Consume the current token if its kind equals `want`.
52    fn eat(&mut self, want: &TokenKind) -> bool {
53        if self.peek() == Some(want) {
54            self.pos += 1;
55            true
56        } else {
57            false
58        }
59    }
60
61    fn expect(&mut self, want: &TokenKind, what: &str) -> Result<()> {
62        if self.eat(want) {
63            Ok(())
64        } else {
65            Err(ParseError::new(
66                format!("expected {what}"),
67                self.current_span(),
68            ))
69        }
70    }
71
72    fn error_here(&self, msg: impl Into<String>) -> ParseError {
73        ParseError::new(msg, self.current_span())
74    }
75
76    // --- object path ---
77
78    pub(crate) fn parse_object_path(&mut self) -> Result<ObjectPath> {
79        // object-type
80        let object_type = match self.advance().map(|t| &t.kind) {
81            Some(TokenKind::Identifier(s)) => s.clone(),
82            _ => return Err(self.error_here("expected object type identifier")),
83        };
84        self.expect(&TokenKind::Colon, "':' after object type")?;
85
86        // first path component (identifier or quoted string)
87        let mut steps = Vec::new();
88        steps.push(PathStep::Key(self.parse_key_component()?));
89
90        // subsequent steps
91        loop {
92            match self.peek() {
93                Some(TokenKind::Dot) => {
94                    self.advance();
95                    steps.push(PathStep::Key(self.parse_key_component()?));
96                }
97                Some(TokenKind::LBracket) => {
98                    self.advance();
99                    let step = match self.peek() {
100                        Some(TokenKind::Star) => {
101                            self.advance();
102                            PathStep::AnyIndex
103                        }
104                        Some(TokenKind::Integer(n)) => {
105                            let n = *n;
106                            self.advance();
107                            if n < 0 {
108                                return Err(self.error_here("list index must be non-negative"));
109                            }
110                            PathStep::Index(n as u64)
111                        }
112                        _ => return Err(self.error_here("expected index or '*' in '[...]'")),
113                    };
114                    self.expect(&TokenKind::RBracket, "']' to close index")?;
115                    steps.push(step);
116                }
117                _ => break,
118            }
119        }
120        Ok(ObjectPath { object_type, steps })
121    }
122
123    fn parse_key_component(&mut self) -> Result<String> {
124        match self.advance().map(|t| &t.kind) {
125            Some(TokenKind::Identifier(s)) => Ok(s.clone()),
126            Some(TokenKind::String(s)) => Ok(s.clone()),
127            _ => Err(self.error_here("expected property name")),
128        }
129    }
130
131    // --- comparison expressions ---
132
133    pub(crate) fn parse_comparison_expression(&mut self) -> Result<ComparisonExpression> {
134        let mut left = self.parse_comparison_and()?;
135        while self.eat(&TokenKind::Or) {
136            let right = self.parse_comparison_and()?;
137            left = ComparisonExpression::Or(Box::new(left), Box::new(right));
138        }
139        Ok(left)
140    }
141
142    fn parse_comparison_and(&mut self) -> Result<ComparisonExpression> {
143        let mut left = self.parse_prop_test()?;
144        while self.eat(&TokenKind::And) {
145            let right = self.parse_prop_test()?;
146            left = ComparisonExpression::And(Box::new(left), Box::new(right));
147        }
148        Ok(left)
149    }
150
151    fn parse_prop_test(&mut self) -> Result<ComparisonExpression> {
152        // Parenthesized sub-expression
153        if self.eat(&TokenKind::LParen) {
154            let inner = self.parse_comparison_expression()?;
155            self.expect(&TokenKind::RParen, "')' to close comparison group")?;
156            return Ok(inner);
157        }
158
159        // EXISTS objectPath
160        if self.eat(&TokenKind::Exists) {
161            let path = self.parse_object_path()?;
162            return Ok(ComparisonExpression::Test(Comparison {
163                path,
164                operator: ComparisonOperator::Exists,
165                negated: false,
166                // operand unused for EXISTS; use a benign placeholder.
167                value: ComparisonOperand::Literal(Literal::Boolean(true)),
168            }));
169        }
170
171        // objectPath NOT? operator operand
172        let path = self.parse_object_path()?;
173        let negated = self.eat(&TokenKind::Not);
174        let operator = self.parse_comparison_operator()?;
175        let value = if operator == ComparisonOperator::In {
176            self.parse_set_literal()?
177        } else {
178            ComparisonOperand::Literal(self.parse_literal()?)
179        };
180        Ok(ComparisonExpression::Test(Comparison {
181            path,
182            operator,
183            negated,
184            value,
185        }))
186    }
187
188    fn parse_comparison_operator(&mut self) -> Result<ComparisonOperator> {
189        let op = match self.peek() {
190            Some(TokenKind::Equal) => ComparisonOperator::Equal,
191            Some(TokenKind::NotEqual) => ComparisonOperator::NotEqual,
192            Some(TokenKind::GreaterThan) => ComparisonOperator::GreaterThan,
193            Some(TokenKind::GreaterThanOrEqual) => ComparisonOperator::GreaterThanOrEqual,
194            Some(TokenKind::LessThan) => ComparisonOperator::LessThan,
195            Some(TokenKind::LessThanOrEqual) => ComparisonOperator::LessThanOrEqual,
196            Some(TokenKind::In) => ComparisonOperator::In,
197            Some(TokenKind::Like) => ComparisonOperator::Like,
198            Some(TokenKind::Matches) => ComparisonOperator::Matches,
199            Some(TokenKind::IsSubset) => ComparisonOperator::IsSubset,
200            Some(TokenKind::IsSuperset) => ComparisonOperator::IsSuperset,
201            _ => return Err(self.error_here("expected a comparison operator")),
202        };
203        self.advance();
204        Ok(op)
205    }
206
207    fn parse_set_literal(&mut self) -> Result<ComparisonOperand> {
208        self.expect(&TokenKind::LParen, "'(' to open set literal")?;
209        let mut items = vec![self.parse_literal()?];
210        while self.eat(&TokenKind::Comma) {
211            items.push(self.parse_literal()?);
212        }
213        self.expect(&TokenKind::RParen, "')' to close set literal")?;
214        Ok(ComparisonOperand::Set(items))
215    }
216
217    fn parse_literal(&mut self) -> Result<Literal> {
218        let lit = match self.peek() {
219            Some(TokenKind::String(s)) => Literal::String(s.clone()),
220            Some(TokenKind::Integer(n)) => Literal::Integer(*n),
221            Some(TokenKind::Float(f)) => Literal::Float(*f),
222            Some(TokenKind::Boolean(b)) => Literal::Boolean(*b),
223            Some(TokenKind::Timestamp(s)) => Literal::Timestamp(s.clone()),
224            Some(TokenKind::Binary(s)) => Literal::Binary(s.clone()),
225            Some(TokenKind::Hex(s)) => Literal::Hex(s.clone()),
226            _ => return Err(self.error_here("expected a literal value")),
227        };
228        self.advance();
229        Ok(lit)
230    }
231
232    // --- observation expressions ---
233
234    pub(crate) fn parse_observation_expression(&mut self) -> Result<ObservationExpression> {
235        let mut left = self.parse_observation_or()?;
236        while self.eat(&TokenKind::FollowedBy) {
237            let right = self.parse_observation_or()?;
238            left = ObservationExpression::FollowedBy(Box::new(left), Box::new(right));
239        }
240        Ok(left)
241    }
242
243    fn parse_observation_or(&mut self) -> Result<ObservationExpression> {
244        let mut left = self.parse_observation_and()?;
245        while self.eat(&TokenKind::Or) {
246            let right = self.parse_observation_and()?;
247            left = ObservationExpression::Or(Box::new(left), Box::new(right));
248        }
249        Ok(left)
250    }
251
252    fn parse_observation_and(&mut self) -> Result<ObservationExpression> {
253        let mut left = self.parse_observation_qualified()?;
254        while self.eat(&TokenKind::And) {
255            let right = self.parse_observation_qualified()?;
256            left = ObservationExpression::And(Box::new(left), Box::new(right));
257        }
258        Ok(left)
259    }
260
261    fn parse_observation_qualified(&mut self) -> Result<ObservationExpression> {
262        let mut expr = self.parse_observation_primary()?;
263        loop {
264            let qualifier = match self.peek() {
265                Some(TokenKind::Within) => {
266                    self.advance();
267                    let seconds = self.parse_number_as_f64()?;
268                    self.expect(&TokenKind::Seconds, "SECONDS after WITHIN value")?;
269                    Qualifier::Within { seconds }
270                }
271                Some(TokenKind::Repeats) => {
272                    self.advance();
273                    let count = self.parse_non_negative_int()?;
274                    self.expect(&TokenKind::Times, "TIMES after REPEATS value")?;
275                    Qualifier::Repeats { count }
276                }
277                Some(TokenKind::Start) => {
278                    self.advance();
279                    let start = self.parse_timestamp_string()?;
280                    self.expect(&TokenKind::Stop, "STOP after START timestamp")?;
281                    let stop = self.parse_timestamp_string()?;
282                    Qualifier::StartStop { start, stop }
283                }
284                _ => break,
285            };
286            expr = ObservationExpression::Qualified {
287                expression: Box::new(expr),
288                qualifier,
289            };
290        }
291        Ok(expr)
292    }
293
294    fn parse_observation_primary(&mut self) -> Result<ObservationExpression> {
295        if self.eat(&TokenKind::LBracket) {
296            let comp = self.parse_comparison_expression()?;
297            self.expect(&TokenKind::RBracket, "']' to close observation")?;
298            return Ok(ObservationExpression::Observation(Box::new(comp)));
299        }
300        if self.eat(&TokenKind::LParen) {
301            let inner = self.parse_observation_expression()?;
302            self.expect(&TokenKind::RParen, "')' to close grouped observation")?;
303            return Ok(inner);
304        }
305        Err(self.error_here("expected '[' or '(' to start an observation"))
306    }
307
308    fn parse_number_as_f64(&mut self) -> Result<f64> {
309        match self.peek() {
310            Some(TokenKind::Integer(n)) => {
311                let v = *n as f64;
312                self.advance();
313                Ok(v)
314            }
315            Some(TokenKind::Float(f)) => {
316                let v = *f;
317                self.advance();
318                Ok(v)
319            }
320            _ => Err(self.error_here("expected a numeric value")),
321        }
322    }
323
324    fn parse_non_negative_int(&mut self) -> Result<u64> {
325        match self.peek() {
326            Some(TokenKind::Integer(n)) if *n >= 0 => {
327                let v = *n as u64;
328                self.advance();
329                Ok(v)
330            }
331            _ => Err(self.error_here("expected a non-negative integer")),
332        }
333    }
334
335    fn parse_timestamp_string(&mut self) -> Result<String> {
336        match self.peek() {
337            Some(TokenKind::Timestamp(s)) => {
338                let v = s.clone();
339                self.advance();
340                Ok(v)
341            }
342            _ => Err(self.error_here("expected a t'...' timestamp literal")),
343        }
344    }
345}
346
347/// Parse a complete pattern string into an AST.
348pub fn parse(src: &str) -> Result<Pattern> {
349    let tokens = crate::lexer::tokenize(src)?;
350    let mut parser = Parser::new(&tokens, src);
351    let expression = parser.parse_observation_expression()?;
352    if !parser.at_end() {
353        return Err(parser.error_here("unexpected trailing tokens after pattern"));
354    }
355    Ok(Pattern { expression })
356}
357
358#[cfg(test)]
359mod tests {
360    use super::*;
361    use crate::ast::PathStep;
362
363    fn parse_path(src: &str) -> crate::ast::ObjectPath {
364        let toks = crate::lexer::tokenize(src).unwrap();
365        let mut p = Parser::new(&toks, src);
366        p.parse_object_path().unwrap()
367    }
368
369    #[test]
370    fn parses_simple_path() {
371        let path = parse_path("ipv4-addr:value");
372        assert_eq!(path.object_type, "ipv4-addr");
373        assert_eq!(path.steps, vec![PathStep::Key("value".to_string())]);
374    }
375
376    #[test]
377    fn parses_nested_keys() {
378        let path = parse_path("file:hashes.MD5");
379        assert_eq!(path.object_type, "file");
380        assert_eq!(
381            path.steps,
382            vec![
383                PathStep::Key("hashes".to_string()),
384                PathStep::Key("MD5".to_string())
385            ]
386        );
387    }
388
389    #[test]
390    fn parses_index_and_any_index() {
391        let path = parse_path("network-traffic:protocols[0]");
392        assert_eq!(
393            path.steps,
394            vec![PathStep::Key("protocols".to_string()), PathStep::Index(0)]
395        );
396
397        let path = parse_path("x:list[*]");
398        assert_eq!(
399            path.steps,
400            vec![PathStep::Key("list".to_string()), PathStep::AnyIndex]
401        );
402    }
403
404    #[test]
405    fn parses_quoted_key() {
406        let path = parse_path("file:hashes.'SHA-256'");
407        assert_eq!(
408            path.steps,
409            vec![
410                PathStep::Key("hashes".to_string()),
411                PathStep::Key("SHA-256".to_string())
412            ]
413        );
414    }
415
416    use crate::ast::{
417        Comparison, ComparisonExpression, ComparisonOperand, ComparisonOperator, Literal,
418    };
419
420    fn parse_comp(src: &str) -> ComparisonExpression {
421        let toks = crate::lexer::tokenize(src).unwrap();
422        let mut p = Parser::new(&toks, src);
423        p.parse_comparison_expression().unwrap()
424    }
425
426    #[test]
427    fn parses_single_comparison() {
428        let c = parse_comp("ipv4-addr:value = '1.2.3.4'");
429        match c {
430            ComparisonExpression::Test(Comparison {
431                operator,
432                negated,
433                value,
434                ..
435            }) => {
436                assert_eq!(operator, ComparisonOperator::Equal);
437                assert!(!negated);
438                assert_eq!(
439                    value,
440                    ComparisonOperand::Literal(Literal::String("1.2.3.4".into()))
441                );
442            }
443            _ => panic!("expected a single test"),
444        }
445    }
446
447    #[test]
448    fn parses_not_operator() {
449        let c = parse_comp("file:size != 0");
450        match c {
451            ComparisonExpression::Test(Comparison {
452                operator, value, ..
453            }) => {
454                assert_eq!(operator, ComparisonOperator::NotEqual);
455                assert_eq!(value, ComparisonOperand::Literal(Literal::Integer(0)));
456            }
457            _ => panic!("expected test"),
458        }
459    }
460
461    #[test]
462    fn parses_not_keyword_prefix() {
463        // `objectPath NOT op value` sets negated = true
464        let c = parse_comp("file:name NOT = 'x'");
465        match c {
466            ComparisonExpression::Test(Comparison { negated, .. }) => assert!(negated),
467            _ => panic!("expected test"),
468        }
469    }
470
471    #[test]
472    fn parses_in_set() {
473        let c = parse_comp("ipv4-addr:value IN ('1.1.1.1', '8.8.8.8')");
474        match c {
475            ComparisonExpression::Test(Comparison {
476                operator, value, ..
477            }) => {
478                assert_eq!(operator, ComparisonOperator::In);
479                assert_eq!(
480                    value,
481                    ComparisonOperand::Set(vec![
482                        Literal::String("1.1.1.1".into()),
483                        Literal::String("8.8.8.8".into()),
484                    ])
485                );
486            }
487            _ => panic!("expected test"),
488        }
489    }
490
491    #[test]
492    fn parses_exists() {
493        let c = parse_comp("EXISTS file:name");
494        match c {
495            ComparisonExpression::Test(Comparison { operator, path, .. }) => {
496                assert_eq!(operator, ComparisonOperator::Exists);
497                assert_eq!(path.object_type, "file");
498            }
499            _ => panic!("expected test"),
500        }
501    }
502
503    #[test]
504    fn comparison_and_binds_tighter_than_or() {
505        // a OR b AND c  =>  a OR (b AND c)
506        let c = parse_comp("file:name = 'a' OR file:name = 'b' AND file:size = 1");
507        match c {
508            ComparisonExpression::Or(_, right) => match *right {
509                ComparisonExpression::And(_, _) => {}
510                _ => panic!("right side of OR should be an AND"),
511            },
512            _ => panic!("top should be OR"),
513        }
514    }
515
516    #[test]
517    fn parses_parenthesized_comparison() {
518        let c = parse_comp("(file:name = 'a' OR file:name = 'b') AND file:size = 1");
519        match c {
520            ComparisonExpression::And(left, _) => match *left {
521                ComparisonExpression::Or(_, _) => {}
522                _ => panic!("left of AND should be OR"),
523            },
524            _ => panic!("top should be AND"),
525        }
526    }
527
528    use crate::ast::{ObservationExpression, Qualifier};
529    use crate::parser::parse;
530
531    #[test]
532    fn parses_single_observation() {
533        let p = parse("[ipv4-addr:value = '1.2.3.4']").unwrap();
534        match p.expression {
535            ObservationExpression::Observation(_) => {}
536            _ => panic!("expected single observation"),
537        }
538    }
539
540    #[test]
541    fn observation_and_binds_tighter_than_or() {
542        // [a] OR [b] AND [c] => [a] OR ([b] AND [c])
543        let p = parse("[file:name='a'] OR [file:name='b'] AND [file:size=1]").unwrap();
544        match p.expression {
545            ObservationExpression::Or(_, right) => match *right {
546                ObservationExpression::And(_, _) => {}
547                _ => panic!("right of OR should be AND"),
548            },
549            _ => panic!("top should be OR"),
550        }
551    }
552
553    #[test]
554    fn followedby_is_loosest() {
555        // [a] FOLLOWEDBY [b] OR [c] => [a] FOLLOWEDBY ([b] OR [c])
556        let p = parse("[file:name='a'] FOLLOWEDBY [file:name='b'] OR [file:name='c']").unwrap();
557        match p.expression {
558            ObservationExpression::FollowedBy(_, right) => match *right {
559                ObservationExpression::Or(_, _) => {}
560                _ => panic!("right of FOLLOWEDBY should be OR"),
561            },
562            _ => panic!("top should be FOLLOWEDBY"),
563        }
564    }
565
566    #[test]
567    fn parses_parenthesized_observation() {
568        let p = parse("([file:name='a'] OR [file:name='b']) FOLLOWEDBY [file:size=1]").unwrap();
569        match p.expression {
570            ObservationExpression::FollowedBy(left, _) => match *left {
571                ObservationExpression::Or(_, _) => {}
572                _ => panic!("left should be OR"),
573            },
574            _ => panic!("top should be FOLLOWEDBY"),
575        }
576    }
577
578    #[test]
579    fn parses_within_qualifier() {
580        let p = parse("[file:name='a'] REPEATS 2 TIMES WITHIN 60 SECONDS").unwrap();
581        // Outermost qualifier is the last one parsed (WITHIN), wrapping REPEATS.
582        match p.expression {
583            ObservationExpression::Qualified {
584                qualifier: Qualifier::Within { seconds },
585                expression,
586            } => {
587                assert_eq!(seconds, 60.0);
588                match *expression {
589                    ObservationExpression::Qualified {
590                        qualifier: Qualifier::Repeats { count },
591                        ..
592                    } => {
593                        assert_eq!(count, 2);
594                    }
595                    _ => panic!("inner should be REPEATS"),
596                }
597            }
598            _ => panic!("outer should be WITHIN"),
599        }
600    }
601
602    #[test]
603    fn parses_start_stop_qualifier() {
604        let p = parse("[file:name='a'] START t'2020-01-01T00:00:00Z' STOP t'2020-01-02T00:00:00Z'")
605            .unwrap();
606        match p.expression {
607            ObservationExpression::Qualified {
608                qualifier: Qualifier::StartStop { start, stop },
609                ..
610            } => {
611                assert_eq!(start, "2020-01-01T00:00:00Z");
612                assert_eq!(stop, "2020-01-02T00:00:00Z");
613            }
614            _ => panic!("expected START..STOP"),
615        }
616    }
617
618    #[test]
619    fn trailing_tokens_error() {
620        assert!(parse("[file:name='a'] [file:name='b']").is_err());
621    }
622}
stix_pattern/parser.rs

stix_pattern/
parser.rs
