stix_pattern/
ast.rs

1//! Abstract syntax tree for STIX 2.1 patterns. All nodes are serde-serializable.
2
3use serde::{Deserialize, Serialize};
4
5use crate::error::Span;
6
7/// A complete parsed pattern.
8#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
9pub struct Pattern {
10    /// The top-level observation expression.
11    pub expression: ObservationExpression,
12}
13
14/// Observation-level expression tree.
15/// `FOLLOWEDBY`/`AND`/`OR` combine observations; qualifiers attach to a sub-expression.
16///
17/// # Chain nodes
18///
19/// `And`, `Or` and `FollowedBy` are n-ary: a chain such as `a OR b OR c` is a
20/// single node holding every operand in source order, so the tree's depth does
21/// not grow with the length of a chain. Nodes produced by [`parse`](crate::parse)
22/// uphold two invariants:
23///
24/// - the operand list has **at least two** elements;
25/// - the **first** operand is never a node of the same operator. Left-nested
26///   chains are flattened (`(a OR b) OR c` and `a OR b OR c` are both
27///   `Or([a, b, c])`), while a right-nested group keeps its own node
28///   (`a OR (b OR c)` is `Or([a, Or([b, c])])`).
29///
30/// A chain `Op([a, b, c])` means the left-associative `(a op b) op c`.
31///
32/// In JSON a two-operand chain serializes as `{"Or": [l, r]}`, and longer
33/// chains as longer arrays.
34#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
35pub enum ObservationExpression {
36    /// A single `[ comparisonExpr ]` observation.
37    Observation {
38        /// The comparison expression inside the brackets.
39        expression: Box<ComparisonExpression>,
40        /// Byte range of the whole `[...]` including the brackets.
41        span: Span,
42    },
43    /// `AND` of two or more observation expressions (see [chain nodes](Self#chain-nodes)).
44    And(Vec<ObservationExpression>),
45    /// `OR` of two or more observation expressions (see [chain nodes](Self#chain-nodes)).
46    Or(Vec<ObservationExpression>),
47    /// `FOLLOWEDBY` of two or more observation expressions: each operand's
48    /// observations precede the next's (see [chain nodes](Self#chain-nodes)).
49    FollowedBy(Vec<ObservationExpression>),
50    /// A sub-expression with a postfix [`Qualifier`] attached.
51    Qualified {
52        /// The qualified sub-expression.
53        expression: Box<ObservationExpression>,
54        /// The attached qualifier.
55        qualifier: Qualifier,
56        /// Byte range of the qualifier clause only (e.g. `WITHIN 60 SECONDS`).
57        span: Span,
58    },
59}
60
61/// Postfix qualifier on an observation expression.
62#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
63pub enum Qualifier {
64    /// `WITHIN <seconds> SECONDS`
65    Within {
66        /// The window length in seconds.
67        seconds: f64,
68    },
69    /// `REPEATS <count> TIMES`
70    Repeats {
71        /// The required repetition count.
72        count: u64,
73    },
74    /// `START <start> STOP <stop>` (RFC3339 timestamps, kept as strings here)
75    StartStop {
76        /// The inclusive window start timestamp.
77        start: String,
78        /// The exclusive window stop timestamp.
79        stop: String,
80    },
81}
82
83/// Comparison-level expression tree (inside `[ ]`).
84///
85/// `And` and `Or` are n-ary chain nodes with the same invariants as
86/// [`ObservationExpression`]'s: at least two operands, and the first operand is
87/// never a node of the same operator.
88#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
89pub enum ComparisonExpression {
90    /// A single property test.
91    Test(Comparison),
92    /// `AND` of two or more comparison expressions.
93    And(Vec<ComparisonExpression>),
94    /// `OR` of two or more comparison expressions.
95    Or(Vec<ComparisonExpression>),
96}
97
98/// A single property test.
99#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
100pub struct Comparison {
101    /// The object path on the left-hand side.
102    pub path: ObjectPath,
103    /// The comparison operator.
104    pub operator: ComparisonOperator,
105    /// `true` if a `NOT` preceded the operator.
106    pub negated: bool,
107    /// The right-hand-side operand.
108    pub value: ComparisonOperand,
109    /// Byte range of the whole property test in the source pattern.
110    pub span: Span,
111}
112
113/// Right-hand side of a comparison: either a single literal or a set (for `IN`).
114#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
115pub enum ComparisonOperand {
116    /// A single literal value.
117    Literal(Literal),
118    /// A parenthesized set of literals (for `IN`).
119    Set(Vec<Literal>),
120}
121
122/// The operator of a property test.
123#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
124pub enum ComparisonOperator {
125    /// `=`
126    Equal,
127    /// `!=` or `<>`
128    NotEqual,
129    /// `>`
130    GreaterThan,
131    /// `>=`
132    GreaterThanOrEqual,
133    /// `<`
134    LessThan,
135    /// `<=`
136    LessThanOrEqual,
137    /// `IN`: membership in a set of literals.
138    In,
139    /// `LIKE`: SQL-style wildcard match (`%`, `_`).
140    Like,
141    /// `MATCHES`: regular-expression match.
142    Matches,
143    /// `ISSUBSET`: IP address/range containment.
144    IsSubset,
145    /// `ISSUPERSET`: inverse IP address/range containment.
146    IsSuperset,
147    /// `EXISTS objectPath`; for this operator the operand is ignored.
148    Exists,
149}
150
151/// An object path: `object-type:first.step[0].next`.
152#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
153pub struct ObjectPath {
154    /// The STIX object type before the colon (e.g. `file`).
155    pub object_type: String,
156    /// The property steps after the colon, in order.
157    pub steps: Vec<PathStep>,
158    /// Byte range of the path text in the source pattern.
159    pub span: Span,
160}
161
162/// One step in an [`ObjectPath`].
163#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
164pub enum PathStep {
165    /// `.key` or the first component after the colon.
166    Key(String),
167    /// `[n]`
168    Index(u64),
169    /// `[*]`
170    AnyIndex,
171}
172
173/// A primitive literal value.
174#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
175pub enum Literal {
176    /// A single-quoted string literal.
177    String(String),
178    /// An integer literal.
179    Integer(i64),
180    /// A floating-point literal.
181    Float(f64),
182    /// A `true`/`false` literal.
183    Boolean(bool),
184    /// RFC3339 timestamp from a `t'...'` literal (kept as the inner string).
185    Timestamp(String),
186    /// Base64 payload from a `b'...'` literal (kept as the inner string).
187    Binary(String),
188    /// Hex payload from an `h'...'` literal (kept as the inner string).
189    Hex(String),
190}
191
192/// A span of zero length at offset 0, used as the normalized value by
193/// [`Pattern::without_spans`].
194const ZERO_SPAN: Span = Span { start: 0, end: 0 };
195
196impl Pattern {
197    /// A copy of this pattern with every source span zeroed.
198    ///
199    /// Two patterns that differ only in whitespace or in where they appeared in
200    /// a source string compare equal after this normalization. Used to state
201    /// structural equality independent of byte offsets.
202    pub fn without_spans(&self) -> Pattern {
203        let mut pattern = self.clone();
204        zero_observation_spans(&mut pattern.expression);
205        pattern
206    }
207}
208
209// The span-zeroing walks use an explicit stack, so neither nesting depth nor
210// chain length costs them any call stack.
211
212fn zero_observation_spans(root: &mut ObservationExpression) {
213    use ObservationExpression as O;
214    let mut pending = vec![root];
215    while let Some(e) = pending.pop() {
216        match e {
217            O::Observation { expression, span } => {
218                *span = ZERO_SPAN;
219                zero_comparison_spans(expression);
220            }
221            O::And(xs) | O::Or(xs) | O::FollowedBy(xs) => pending.extend(xs.iter_mut()),
222            O::Qualified {
223                expression, span, ..
224            } => {
225                *span = ZERO_SPAN;
226                pending.push(expression);
227            }
228        }
229    }
230}
231
232fn zero_comparison_spans(root: &mut ComparisonExpression) {
233    use ComparisonExpression as C;
234    let mut pending = vec![root];
235    while let Some(e) = pending.pop() {
236        match e {
237            C::Test(c) => {
238                c.span = ZERO_SPAN;
239                c.path.span = ZERO_SPAN;
240            }
241            C::And(xs) | C::Or(xs) => pending.extend(xs.iter_mut()),
242        }
243    }
244}
245
246#[cfg(test)]
247mod tests {
248    use super::*;
249
250    #[test]
251    fn build_simple_comparison_pattern() {
252        let path = ObjectPath {
253            object_type: "ipv4-addr".to_string(),
254            steps: vec![PathStep::Key("value".to_string())],
255            span: Span::default(),
256        };
257        let comp = Comparison {
258            path,
259            operator: ComparisonOperator::Equal,
260            negated: false,
261            value: ComparisonOperand::Literal(Literal::String("1.2.3.4".to_string())),
262            span: Span::default(),
263        };
264        let pattern = Pattern {
265            expression: ObservationExpression::Observation {
266                expression: Box::new(ComparisonExpression::Test(comp)),
267                span: Span::default(),
268            },
269        };
270        match pattern.expression {
271            ObservationExpression::Observation { .. } => {}
272            _ => panic!("expected observation"),
273        }
274    }
275
276    fn obs(value: &str) -> ObservationExpression {
277        ObservationExpression::Observation {
278            expression: Box::new(ComparisonExpression::Test(Comparison {
279                path: ObjectPath {
280                    object_type: "x".to_string(),
281                    steps: vec![PathStep::Key("v".to_string())],
282                    span: Span::default(),
283                },
284                operator: ComparisonOperator::Equal,
285                negated: false,
286                value: ComparisonOperand::Literal(Literal::String(value.to_string())),
287                span: Span::default(),
288            })),
289            span: Span::default(),
290        }
291    }
292
293    /// The JSON of a two-operand chain is exactly what the old binary
294    /// `Or(Box, Box)` produced; longer chains are longer arrays.
295    #[test]
296    fn chain_json_shape_is_pinned() {
297        let leaf = |v: &str| serde_json::to_string(&obs(v)).unwrap();
298        let two = ObservationExpression::Or(vec![obs("a"), obs("b")]);
299        assert_eq!(
300            serde_json::to_string(&two).unwrap(),
301            format!("{{\"Or\":[{},{}]}}", leaf("a"), leaf("b"))
302        );
303        let three = ObservationExpression::FollowedBy(vec![obs("a"), obs("b"), obs("c")]);
304        assert_eq!(
305            serde_json::to_string(&three).unwrap(),
306            format!(
307                "{{\"FollowedBy\":[{},{},{}]}}",
308                leaf("a"),
309                leaf("b"),
310                leaf("c")
311            )
312        );
313        let back: ObservationExpression =
314            serde_json::from_str(&serde_json::to_string(&three).unwrap()).unwrap();
315        assert_eq!(back, three);
316    }
317
318    #[test]
319    fn ast_round_trips_through_json() {
320        let lit = Literal::Integer(42);
321        let json = serde_json::to_string(&lit).unwrap();
322        let back: Literal = serde_json::from_str(&json).unwrap();
323        assert_eq!(lit, back);
324    }
325}
stix_pattern/ast.rs

stix_pattern/
ast.rs
