stix_pattern/ir/
lower.rs

1//! Lowering: AST to [`Program`].
2
3use crate::ast::{
4    Comparison, ComparisonExpression, ComparisonOperand, ComparisonOperator, ObservationExpression,
5    Pattern, Qualifier,
6};
7use crate::error::Span;
8use crate::ir::{
9    Block, BlockId, BlockKind, InstrId, Instruction, Op, Operand, Program, SCHEMA_VERSION,
10};
11
12/// Lower a parsed pattern into its three-address representation.
13///
14/// This is total for every [`Pattern`] that satisfies the AST invariants, which
15/// [`parse`](crate::parse) guarantees. The result always satisfies
16/// [`Program::validate`](crate::ir::Program::validate).
17///
18/// Each n-ary chain node becomes the left-associative chain of binary
19/// operations it stands for, so `a OR b OR c` lowers to `Or(Or(a, b), c)`.
20///
21/// # Panics
22///
23/// If a chain node has no operands. This can only happen in hand-built or
24/// deserialized [`Pattern`]s that violate the AST invariants.
25pub fn lower(pattern: &Pattern) -> Program {
26    let mut l = Lowerer {
27        next_instr: 0,
28        next_block: 0,
29        blocks: Vec::new(),
30    };
31    let main_id = l.fresh_block();
32    let mut main_instrs = Vec::new();
33    let result = l.lower_observation(&pattern.expression, &mut main_instrs);
34    l.push(&mut main_instrs, Op::Ret { value: result }, None);
35    Program {
36        schema_version: SCHEMA_VERSION,
37        blocks: l.blocks,
38        main: Block {
39            id: main_id,
40            kind: BlockKind::Main,
41            instructions: main_instrs,
42        },
43    }
44}
45
46/// An AST node that lowers to a single value: lets [`Lowerer::lower_chain`]
47/// serve both the observation and the comparison level.
48trait Lowerable {
49    fn lower_into(&self, l: &mut Lowerer, into: &mut Vec<Instruction>) -> InstrId;
50}
51
52impl Lowerable for ObservationExpression {
53    fn lower_into(&self, l: &mut Lowerer, into: &mut Vec<Instruction>) -> InstrId {
54        l.lower_observation(self, into)
55    }
56}
57
58impl Lowerable for ComparisonExpression {
59    fn lower_into(&self, l: &mut Lowerer, into: &mut Vec<Instruction>) -> InstrId {
60        l.lower_comparison(self, into)
61    }
62}
63
64struct Lowerer {
65    next_instr: u32,
66    next_block: u32,
67    blocks: Vec<Block>,
68}
69
70impl Lowerer {
71    fn fresh_block(&mut self) -> BlockId {
72        let id = BlockId(self.next_block);
73        self.next_block += 1;
74        id
75    }
76
77    /// Append an instruction and return the id naming its result.
78    fn push(&mut self, into: &mut Vec<Instruction>, op: Op, span: Option<Span>) -> InstrId {
79        let id = InstrId(self.next_instr);
80        self.next_instr += 1;
81        into.push(Instruction { id, op, span });
82        id
83    }
84
85    fn lower_observation(
86        &mut self,
87        e: &ObservationExpression,
88        into: &mut Vec<Instruction>,
89    ) -> InstrId {
90        match e {
91            ObservationExpression::Observation { expression, span } => {
92                let block = self.lower_comparison_block(expression);
93                self.push(into, Op::Observe { block }, Some(*span))
94            }
95            ObservationExpression::And(xs) => {
96                self.lower_chain(xs, into, |lhs, rhs| Op::And { lhs, rhs })
97            }
98            ObservationExpression::Or(xs) => {
99                self.lower_chain(xs, into, |lhs, rhs| Op::Or { lhs, rhs })
100            }
101            ObservationExpression::FollowedBy(xs) => {
102                self.lower_chain(xs, into, |lhs, rhs| Op::FollowedBy { lhs, rhs })
103            }
104            ObservationExpression::Qualified {
105                expression,
106                qualifier,
107                span,
108            } => {
109                let input = self.lower_observation(expression, into);
110                let op = match qualifier {
111                    Qualifier::Within { seconds } => Op::Within {
112                        input,
113                        seconds: *seconds,
114                    },
115                    Qualifier::Repeats { count } => Op::Repeats {
116                        input,
117                        count: *count,
118                    },
119                    Qualifier::StartStop { start, stop } => Op::StartStop {
120                        input,
121                        start: start.clone(),
122                        stop: stop.clone(),
123                    },
124                };
125                self.push(into, op, Some(*span))
126            }
127        }
128    }
129
130    /// Lower one `[...]` observation into a fresh comparison block, returning its id.
131    fn lower_comparison_block(&mut self, e: &ComparisonExpression) -> BlockId {
132        let id = self.fresh_block();
133        let mut instrs = Vec::new();
134        let result = self.lower_comparison(e, &mut instrs);
135        self.push(&mut instrs, Op::Yield { value: result }, None);
136        self.blocks.push(Block {
137            id,
138            kind: BlockKind::Comparison,
139            instructions: instrs,
140        });
141        id
142    }
143
144    fn lower_comparison(
145        &mut self,
146        e: &ComparisonExpression,
147        into: &mut Vec<Instruction>,
148    ) -> InstrId {
149        match e {
150            ComparisonExpression::Test(c) => self.lower_test(c, into),
151            ComparisonExpression::And(xs) => {
152                self.lower_chain(xs, into, |lhs, rhs| Op::And { lhs, rhs })
153            }
154            ComparisonExpression::Or(xs) => {
155                self.lower_chain(xs, into, |lhs, rhs| Op::Or { lhs, rhs })
156            }
157        }
158    }
159
160    /// Lower an n-ary chain node as the left-associative binary chain it
161    /// stands for: `[a, b, c]` becomes `op(op(a, b), c)`, emitted in the same
162    /// order as the nested binary form would be. Iterates over the operands,
163    /// so chain length costs no stack.
164    fn lower_chain<E: Lowerable>(
165        &mut self,
166        operands: &[E],
167        into: &mut Vec<Instruction>,
168        op: fn(InstrId, InstrId) -> Op,
169    ) -> InstrId {
170        let (first, rest) = operands
171            .split_first()
172            .expect("chain nodes have at least two operands");
173        let mut acc = first.lower_into(self, into);
174        for operand in rest {
175            let rhs = operand.lower_into(self, into);
176            acc = self.push(into, op(acc, rhs), None);
177        }
178        acc
179    }
180
181    fn lower_test(&mut self, c: &Comparison, into: &mut Vec<Instruction>) -> InstrId {
182        let lhs = self.push(
183            into,
184            Op::Load {
185                path: c.path.clone(),
186            },
187            Some(c.path.span),
188        );
189        // EXISTS carries a placeholder operand in the AST; the IR states its absence.
190        let rhs = if c.operator == ComparisonOperator::Exists {
191            Operand::Absent
192        } else {
193            match &c.value {
194                ComparisonOperand::Literal(lit) => Operand::Literal(lit.clone()),
195                ComparisonOperand::Set(items) => Operand::Set(items.clone()),
196            }
197        };
198        self.push(
199            into,
200            Op::Compare {
201                operator: c.operator,
202                negated: c.negated,
203                lhs,
204                rhs,
205            },
206            Some(c.span),
207        )
208    }
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214    use crate::ast::ComparisonOperator;
215    use crate::ir::{BlockKind, Op, Operand, SCHEMA_VERSION};
216    use crate::parse;
217
218    #[test]
219    fn lowers_a_single_comparison() {
220        let p = parse("[file:size > 1024]").unwrap();
221        let prog = lower(&p);
222
223        assert_eq!(prog.schema_version, SCHEMA_VERSION);
224        assert_eq!(prog.blocks.len(), 1);
225        assert_eq!(prog.blocks[0].kind, BlockKind::Comparison);
226        assert_eq!(prog.main.kind, BlockKind::Main);
227
228        let ops: Vec<&Op> = prog.blocks[0].instructions.iter().map(|i| &i.op).collect();
229        assert!(matches!(ops[0], Op::Load { .. }), "got {:?}", ops[0]);
230        assert!(
231            matches!(
232                ops[1],
233                Op::Compare {
234                    operator: ComparisonOperator::GreaterThan,
235                    negated: false,
236                    ..
237                }
238            ),
239            "got {:?}",
240            ops[1]
241        );
242        assert!(matches!(ops[2], Op::Yield { .. }), "got {:?}", ops[2]);
243
244        let main_ops: Vec<&Op> = prog.main.instructions.iter().map(|i| &i.op).collect();
245        assert!(matches!(main_ops[0], Op::Observe { .. }));
246        assert!(matches!(main_ops[1], Op::Ret { .. }));
247    }
248
249    #[test]
250    fn compare_references_its_load() {
251        let p = parse("[file:size > 1024]").unwrap();
252        let prog = lower(&p);
253        let load_id = prog.blocks[0].instructions[0].id;
254        match &prog.blocks[0].instructions[1].op {
255            Op::Compare { lhs, .. } => assert_eq!(*lhs, load_id),
256            other => panic!("expected a compare, got {other:?}"),
257        }
258    }
259
260    #[test]
261    fn exists_lowers_to_an_absent_operand() {
262        let p = parse("[EXISTS file:name]").unwrap();
263        let prog = lower(&p);
264        match &prog.blocks[0].instructions[1].op {
265            Op::Compare { operator, rhs, .. } => {
266                assert_eq!(*operator, ComparisonOperator::Exists);
267                assert_eq!(*rhs, Operand::Absent);
268            }
269            other => panic!("expected a compare, got {other:?}"),
270        }
271    }
272
273    #[test]
274    fn in_lowers_to_a_set_operand() {
275        let p = parse("[ipv4-addr:value IN ('1.1.1.1', '8.8.8.8')]").unwrap();
276        let prog = lower(&p);
277        match &prog.blocks[0].instructions[1].op {
278            Op::Compare { rhs, .. } => match rhs {
279                Operand::Set(items) => assert_eq!(items.len(), 2),
280                other => panic!("expected a set, got {other:?}"),
281            },
282            other => panic!("expected a compare, got {other:?}"),
283        }
284    }
285
286    #[test]
287    fn each_observation_gets_its_own_block() {
288        let p = parse("[file:name='a'] FOLLOWEDBY [file:name='b']").unwrap();
289        let prog = lower(&p);
290        assert_eq!(prog.blocks.len(), 2);
291        let main_ops: Vec<&Op> = prog.main.instructions.iter().map(|i| &i.op).collect();
292        assert!(matches!(main_ops[0], Op::Observe { .. }));
293        assert!(matches!(main_ops[1], Op::Observe { .. }));
294        assert!(matches!(main_ops[2], Op::FollowedBy { .. }));
295        assert!(matches!(main_ops[3], Op::Ret { .. }));
296    }
297
298    #[test]
299    fn chains_lower_to_left_associative_binary_ops() {
300        let p = parse("[x:v=1] OR [x:v=2] OR [x:v=3]").unwrap();
301        let prog = lower(&p);
302        let main = &prog.main.instructions;
303        let ops: Vec<&Op> = main.iter().map(|i| &i.op).collect();
304        assert!(matches!(ops[0], Op::Observe { .. }));
305        assert!(matches!(ops[1], Op::Observe { .. }));
306        assert_eq!(
307            *ops[2],
308            Op::Or {
309                lhs: main[0].id,
310                rhs: main[1].id
311            }
312        );
313        assert!(matches!(ops[3], Op::Observe { .. }));
314        assert_eq!(
315            *ops[4],
316            Op::Or {
317                lhs: main[2].id,
318                rhs: main[3].id
319            }
320        );
321        assert!(matches!(ops[5], Op::Ret { .. }));
322
323        // The same holds inside a comparison block.
324        let p = parse("[x:v=1 AND x:v=2 AND x:v=3]").unwrap();
325        let block = &lower(&p).blocks[0].instructions;
326        let ands: Vec<&Instruction> = block
327            .iter()
328            .filter(|i| matches!(i.op, Op::And { .. }))
329            .collect();
330        assert_eq!(ands.len(), 2);
331        let Op::And { lhs, .. } = ands[1].op else {
332            unreachable!()
333        };
334        assert_eq!(lhs, ands[0].id);
335    }
336
337    #[test]
338    fn nested_qualifiers_lower_inner_first() {
339        let p = parse("[file:name='a'] REPEATS 2 TIMES WITHIN 60 SECONDS").unwrap();
340        let prog = lower(&p);
341        let main_ops: Vec<&Op> = prog.main.instructions.iter().map(|i| &i.op).collect();
342        assert!(matches!(main_ops[0], Op::Observe { .. }));
343        assert!(matches!(main_ops[1], Op::Repeats { count: 2, .. }));
344        assert!(matches!(main_ops[2], Op::Within { .. }));
345        assert!(matches!(main_ops[3], Op::Ret { .. }));
346    }
347
348    #[test]
349    fn instructions_carry_source_spans() {
350        let src = "[file:size > 1024]";
351        let prog = lower(&parse(src).unwrap());
352        for instr in &prog.blocks[0].instructions {
353            // Yield is synthetic and has no span of its own.
354            if matches!(instr.op, Op::Yield { .. }) {
355                continue;
356            }
357            let span = instr.span.expect("lowered instruction should have a span");
358            assert!(span.end <= src.len());
359            assert!(span.start < span.end, "span should be non-empty");
360        }
361    }
362}
stix_pattern/ir/lower.rs

stix_pattern/ir/
lower.rs
