stix_pattern/ir/
instr.rs

1//! The IR instruction set and its container types.
2
3use serde::{Deserialize, Serialize};
4
5use crate::ast::{ComparisonOperator, Literal, ObjectPath};
6use crate::error::Span;
7
8/// Version of the serialized IR schema. Checked by
9/// [`Program::validate`](crate::ir::Program::validate).
10pub const SCHEMA_VERSION: u32 = 1;
11
12/// Identifies one instruction, and therefore the value it produces.
13///
14/// The IR is in SSA form: there is no separate destination field, so a value is
15/// named by the id of the instruction that computes it.
16#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
17pub struct InstrId(pub u32);
18
19/// Identifies one block within a [`Program`](crate::ir::Program).
20#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
21pub struct BlockId(pub u32);
22
23/// Right-hand side of a [`Op::Compare`].
24#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
25pub enum Operand {
26    /// A single literal value.
27    Literal(Literal),
28    /// A set of literals, for `IN`.
29    Set(Vec<Literal>),
30    /// No operand, for `EXISTS`.
31    Absent,
32}
33
34/// One three-address operation.
35///
36/// Instructions in a [`BlockKind::Comparison`] block use the comparison-tier ops
37/// (`Load`, `Compare`, `And`, `Or`, `Yield`); instructions in the
38/// [`BlockKind::Main`] block use the observation-tier ops. `And` and `Or` are
39/// shared between the tiers and take their evaluation semantics from the
40/// enclosing block's kind.
41#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
42#[serde(tag = "op", rename_all = "snake_case")]
43pub enum Op {
44    /// Resolve an object path to a value.
45    Load {
46        /// The path to resolve.
47        path: ObjectPath,
48    },
49    /// Apply a comparison operator to a loaded value and an operand.
50    Compare {
51        /// The comparison operator.
52        operator: ComparisonOperator,
53        /// `true` if a `NOT` preceded the operator in the source.
54        negated: bool,
55        /// The loaded value being compared.
56        lhs: InstrId,
57        /// The right-hand side.
58        rhs: Operand,
59    },
60    /// Boolean conjunction of two values.
61    And {
62        /// Left operand.
63        lhs: InstrId,
64        /// Right operand.
65        rhs: InstrId,
66    },
67    /// Boolean disjunction of two values.
68    Or {
69        /// Left operand.
70        lhs: InstrId,
71        /// Right operand.
72        rhs: InstrId,
73    },
74    /// Terminator of a comparison block: its result.
75    Yield {
76        /// The value the block evaluates to.
77        value: InstrId,
78    },
79    /// Evaluate a comparison block against an observation.
80    Observe {
81        /// The comparison block to evaluate.
82        block: BlockId,
83    },
84    /// `FOLLOWEDBY`: the left result's observations precede the right's.
85    FollowedBy {
86        /// Left operand.
87        lhs: InstrId,
88        /// Right operand.
89        rhs: InstrId,
90    },
91    /// `WITHIN <seconds> SECONDS` applied to a result.
92    Within {
93        /// The result being qualified.
94        input: InstrId,
95        /// The window length in seconds.
96        seconds: f64,
97    },
98    /// `REPEATS <count> TIMES` applied to a result.
99    Repeats {
100        /// The result being qualified.
101        input: InstrId,
102        /// The required repetition count.
103        count: u64,
104    },
105    /// `START <start> STOP <stop>` applied to a result.
106    StartStop {
107        /// The result being qualified.
108        input: InstrId,
109        /// Inclusive window start, RFC3339.
110        start: String,
111        /// Exclusive window stop, RFC3339.
112        stop: String,
113    },
114    /// Terminator of the main block: the program's result.
115    Ret {
116        /// The value the program evaluates to.
117        value: InstrId,
118    },
119}
120
121/// One instruction: an id, an operation, and optionally where it came from.
122#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
123pub struct Instruction {
124    /// Unique id, which also names this instruction's result.
125    pub id: InstrId,
126    /// The operation.
127    pub op: Op,
128    /// Byte range in the source pattern, when this was lowered from text.
129    pub span: Option<Span>,
130}
131
132/// Which tier a block belongs to.
133#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
134#[serde(rename_all = "snake_case")]
135pub enum BlockKind {
136    /// A `[...]` observation's comparisons, evaluated once per binding set.
137    Comparison,
138    /// The observation-tier block combining observation results.
139    Main,
140}
141
142/// A straight-line sequence of instructions ending in a terminator.
143#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
144pub struct Block {
145    /// Unique id.
146    pub id: BlockId,
147    /// Which tier this block belongs to.
148    pub kind: BlockKind,
149    /// The instructions, in evaluation order.
150    pub instructions: Vec<Instruction>,
151}
152
153/// A lowered pattern: comparison blocks plus the observation-tier block.
154#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
155pub struct Program {
156    /// Serialized schema version; see [`SCHEMA_VERSION`].
157    pub schema_version: u32,
158    /// The comparison blocks, in lowering order.
159    pub blocks: Vec<Block>,
160    /// The observation-tier block.
161    pub main: Block,
162}
163
164/// Counts calls to the linear-scan lookups, so tests can assert that the hot
165/// paths never make one. Thread-local, so parallel tests do not disturb each
166/// other.
167#[cfg(test)]
168pub(crate) mod scans {
169    use std::cell::Cell;
170
171    thread_local!(static COUNT: Cell<usize> = const { Cell::new(0) });
172
173    pub(crate) fn record() {
174        COUNT.with(|c| c.set(c.get() + 1));
175    }
176
177    /// Scans made on this thread since it started.
178    pub(crate) fn count() -> usize {
179        COUNT.with(Cell::get)
180    }
181}
182
183impl Program {
184    /// The comparison block with the given id, if present.
185    pub fn block(&self, id: BlockId) -> Option<&Block> {
186        #[cfg(test)]
187        scans::record();
188        self.blocks.iter().find(|b| b.id == id)
189    }
190}
191
192impl Block {
193    /// The instruction with the given id, if present in this block.
194    pub fn instruction(&self, id: InstrId) -> Option<&Instruction> {
195        #[cfg(test)]
196        scans::record();
197        self.instructions.iter().find(|i| i.id == id)
198    }
199
200    /// The block's terminator — its last instruction — if it has one.
201    pub fn terminator(&self) -> Option<&Instruction> {
202        self.instructions.last()
203    }
204}
205
206#[cfg(test)]
207mod tests {
208    use super::*;
209    use crate::ast::{ComparisonOperator, Literal, ObjectPath, PathStep};
210    use crate::error::Span;
211
212    fn sample_program() -> Program {
213        let path = ObjectPath {
214            object_type: "file".to_string(),
215            steps: vec![PathStep::Key("size".to_string())],
216            span: Span::default(),
217        };
218        Program {
219            schema_version: SCHEMA_VERSION,
220            blocks: vec![Block {
221                id: BlockId(0),
222                kind: BlockKind::Comparison,
223                instructions: vec![
224                    Instruction {
225                        id: InstrId(0),
226                        op: Op::Load { path },
227                        span: None,
228                    },
229                    Instruction {
230                        id: InstrId(1),
231                        op: Op::Compare {
232                            operator: ComparisonOperator::GreaterThan,
233                            negated: false,
234                            lhs: InstrId(0),
235                            rhs: Operand::Literal(Literal::Integer(1024)),
236                        },
237                        span: None,
238                    },
239                    Instruction {
240                        id: InstrId(2),
241                        op: Op::Yield { value: InstrId(1) },
242                        span: None,
243                    },
244                ],
245            }],
246            main: Block {
247                id: BlockId(1),
248                kind: BlockKind::Main,
249                instructions: vec![
250                    Instruction {
251                        id: InstrId(3),
252                        op: Op::Observe { block: BlockId(0) },
253                        span: None,
254                    },
255                    Instruction {
256                        id: InstrId(4),
257                        op: Op::Ret { value: InstrId(3) },
258                        span: None,
259                    },
260                ],
261            },
262        }
263    }
264
265    #[test]
266    fn program_round_trips_through_json() {
267        let p = sample_program();
268        let json = serde_json::to_string(&p).unwrap();
269        let back: Program = serde_json::from_str(&json).unwrap();
270        assert_eq!(p, back);
271    }
272
273    #[test]
274    fn ops_serialize_internally_tagged() {
275        let p = sample_program();
276        let json = serde_json::to_string(&p).unwrap();
277        assert!(json.contains(r#""op":"load""#), "got: {json}");
278        assert!(json.contains(r#""op":"compare""#), "got: {json}");
279        assert!(json.contains(r#""op":"observe""#), "got: {json}");
280    }
281
282    #[test]
283    fn schema_version_is_one() {
284        assert_eq!(SCHEMA_VERSION, 1);
285    }
286}
stix_pattern/ir/instr.rs

stix_pattern/ir/
instr.rs
