stix_pattern/ir/
validate.rs

1//! Well-formedness checking for a [`Program`].
2
3use std::collections::HashSet;
4
5use thiserror::Error;
6
7use crate::ast::{ComparisonOperator, Literal, PathStep};
8use crate::ir::{Block, BlockId, BlockKind, InstrId, Op, Operand, Program, SCHEMA_VERSION};
9
10/// Whether a literal is renderable — i.e. not a non-finite float.
11fn literal_is_finite(lit: &Literal) -> bool {
12    match lit {
13        Literal::Float(f) => f.is_finite(),
14        _ => true,
15    }
16}
17
18/// A way a [`Program`] can be malformed.
19#[derive(Debug, Clone, PartialEq, Eq, Error)]
20pub enum IrError {
21    /// The program's `schema_version` is not one this build understands.
22    #[error("unsupported IR schema version {found} (expected {expected})")]
23    UnsupportedSchemaVersion {
24        /// The version found in the program.
25        found: u32,
26        /// The version this build supports.
27        expected: u32,
28    },
29    /// An instruction referenced a value that is not defined earlier in its block.
30    #[error(
31        "instruction {instr} references value {value}, which is not defined earlier in its block"
32    )]
33    UnknownValue {
34        /// The referencing instruction.
35        instr: u32,
36        /// The referenced value.
37        value: u32,
38    },
39    /// `Observe` targeted a missing block, or one that is not a comparison block.
40    #[error("instruction {instr} observes block {block}, which is not a comparison block")]
41    UnknownBlock {
42        /// The referencing instruction.
43        instr: u32,
44        /// The referenced block.
45        block: u32,
46    },
47    /// A block does not end in the terminator its kind requires.
48    #[error("block {block} does not end in {expected}")]
49    MissingTerminator {
50        /// The offending block.
51        block: u32,
52        /// The terminator the block's kind requires.
53        expected: &'static str,
54    },
55    /// A terminator appeared somewhere other than the end of its block.
56    #[error("block {block} has a terminator at instruction {instr}, which is not its last")]
57    MisplacedTerminator {
58        /// The offending block.
59        block: u32,
60        /// The misplaced terminator.
61        instr: u32,
62    },
63    /// An op appeared in a block of the wrong kind.
64    #[error("instruction {instr} is not valid in a {kind} block")]
65    WrongTier {
66        /// The offending instruction.
67        instr: u32,
68        /// The block kind it appeared in.
69        kind: &'static str,
70    },
71    /// A `Compare`'s operand shape does not match its operator.
72    #[error("instruction {instr} has the wrong operand shape: {detail}")]
73    OperandShape {
74        /// The offending instruction.
75        instr: u32,
76        /// What was expected.
77        detail: &'static str,
78    },
79    /// Two instructions share an id.
80    #[error("instruction id {id} is used more than once")]
81    DuplicateInstrId {
82        /// The repeated id.
83        id: u32,
84    },
85    /// Two blocks share an id.
86    #[error("block id {id} is used more than once")]
87    DuplicateBlockId {
88        /// The repeated id.
89        id: u32,
90    },
91    /// A float that STIX pattern syntax cannot express.
92    ///
93    /// The patterning language has no notation for `NaN` or infinity, so such a
94    /// value could never be rendered back to text.
95    #[error("instruction {instr} holds a non-finite float, which pattern syntax cannot express")]
96    NonFiniteFloat {
97        /// The offending instruction.
98        instr: u32,
99    },
100    /// A `Repeats` count is larger than the pattern lexer can read back.
101    ///
102    /// The lexer reads integer literals as `i64`, so `REPEATS <n> TIMES` parses
103    /// only for `n <= i64::MAX`. A larger count would render to text that does
104    /// not parse. Zero is accepted by the grammar and so is accepted here.
105    #[error("repeats count {count} exceeds i64::MAX, which pattern syntax cannot express")]
106    RepeatsOutOfRange {
107        /// The offending count.
108        count: u64,
109    },
110    /// A `Load` path has a list index larger than the pattern lexer can read back.
111    ///
112    /// The lexer reads integer literals as `i64`, so `[n]` in a path parses only
113    /// for `n <= i64::MAX`. A larger index would render to text that does not parse.
114    #[error("instruction {instr} has path index {index} above i64::MAX, which pattern syntax cannot express")]
115    PathIndexOutOfRange {
116        /// The offending instruction.
117        instr: u32,
118        /// The offending index.
119        index: u64,
120    },
121    /// One value is consumed by more than one operand.
122    ///
123    /// Pattern text has no way to name a shared value, so a shared
124    /// subexpression would have to be re-rendered once per use — making output
125    /// exponential in the number of instructions. Requiring each value to have
126    /// at most one consumer keeps every value expression a tree, which is what
127    /// [`render`](crate::ir::render) already assumes.
128    ///
129    /// This covers values only. A comparison *block* is not a value; its reuse
130    /// is bounded separately, by [`IrError::BlockObservedTwice`].
131    #[error("instruction {instr} references value {value}, which is already used elsewhere")]
132    MultipleUses {
133        /// The referencing instruction.
134        instr: u32,
135        /// The value that was already used.
136        value: u32,
137    },
138    /// A comparison block is the target of more than one `Observe`.
139    ///
140    /// `Observe` names a block rather than a value, so the single-use rule does
141    /// not cover it. Pattern text cannot name a shared block either: each
142    /// `Observe` is rendered as its own copy of the block, so sharing one block
143    /// among *k* observes makes output grow with *k* times the block's size —
144    /// quadratic in the program. Requiring each block to be observed at most
145    /// once keeps rendered size linear. [`lower`](crate::ir::lower) already
146    /// allocates one block per observation.
147    #[error("block {block} is observed more than once")]
148    BlockObservedTwice {
149        /// The block that was observed again.
150        block: u32,
151    },
152    /// A `Compare`'s left-hand side is not a `Load`.
153    ///
154    /// The renderer takes the compared object path from the `Load` it names; any
155    /// other instruction leaves the path missing from the rendered text.
156    #[error("instruction {instr} compares value {lhs}, which is not a load")]
157    ExpectedLoad {
158        /// The offending instruction.
159        instr: u32,
160        /// The value it named as its left-hand side.
161        lhs: u32,
162    },
163    /// An `EXISTS` comparison is marked negated.
164    ///
165    /// The grammar has no negated form of `EXISTS`, so the negation could not be
166    /// rendered and would be silently dropped.
167    #[error("instruction {instr} negates EXISTS, which pattern syntax cannot express")]
168    NegatedExists {
169        /// The offending instruction.
170        instr: u32,
171    },
172    /// A block has the wrong [`BlockKind`](crate::ir::BlockKind) for its position.
173    #[error("block {block} should be {expected}")]
174    WrongBlockKind {
175        /// The offending block.
176        block: u32,
177        /// The kind its position requires.
178        expected: &'static str,
179    },
180}
181
182impl Program {
183    /// Check that this program is well-formed.
184    ///
185    /// Lowered programs always pass. Run this on any program that was built by
186    /// hand or deserialized, since deserialization does not check invariants.
187    ///
188    /// Unreferenced ("dead") instructions are allowed — only dangling and
189    /// forward *references* are errors. A value may have at most one consumer,
190    /// however, and a comparison block at most one `Observe`: see
191    /// [`IrError::MultipleUses`] and [`IrError::BlockObservedTwice`].
192    ///
193    /// Nesting depth is not limited: validation, [`render`](crate::ir::render)
194    /// and [`Program::span_of`] are all iterative, so a deeply nested program
195    /// cannot overflow the stack.
196    pub fn validate(&self) -> Result<(), IrError> {
197        if self.schema_version != SCHEMA_VERSION {
198            return Err(IrError::UnsupportedSchemaVersion {
199                found: self.schema_version,
200                expected: SCHEMA_VERSION,
201            });
202        }
203
204        if self.main.kind != BlockKind::Main {
205            return Err(IrError::WrongBlockKind {
206                block: self.main.id.0,
207                expected: "the main block",
208            });
209        }
210        for b in &self.blocks {
211            if b.kind != BlockKind::Comparison {
212                return Err(IrError::WrongBlockKind {
213                    block: b.id.0,
214                    expected: "a comparison block",
215                });
216            }
217        }
218
219        let mut block_ids = HashSet::new();
220        for b in self.blocks.iter().chain(std::iter::once(&self.main)) {
221            if !block_ids.insert(b.id) {
222                return Err(IrError::DuplicateBlockId { id: b.id.0 });
223            }
224        }
225
226        let comparison_blocks: HashSet<BlockId> = self
227            .blocks
228            .iter()
229            .filter(|b| b.kind == BlockKind::Comparison)
230            .map(|b| b.id)
231            .collect();
232
233        let mut seen_instrs = HashSet::new();
234        let mut used_values = HashSet::new();
235        let mut observed_blocks = HashSet::new();
236        for b in self.blocks.iter().chain(std::iter::once(&self.main)) {
237            self.check_block(
238                b,
239                &comparison_blocks,
240                &mut seen_instrs,
241                &mut used_values,
242                &mut observed_blocks,
243            )?;
244        }
245        Ok(())
246    }
247
248    fn check_block(
249        &self,
250        b: &Block,
251        comparison_blocks: &HashSet<BlockId>,
252        seen_instrs: &mut HashSet<InstrId>,
253        used_values: &mut HashSet<InstrId>,
254        observed_blocks: &mut HashSet<BlockId>,
255    ) -> Result<(), IrError> {
256        let expected_terminator = match b.kind {
257            BlockKind::Comparison => "a yield",
258            BlockKind::Main => "a ret",
259        };
260        let kind_name = match b.kind {
261            BlockKind::Comparison => "comparison",
262            BlockKind::Main => "main",
263        };
264
265        let is_terminator = |op: &Op| match b.kind {
266            BlockKind::Comparison => matches!(op, Op::Yield { .. }),
267            BlockKind::Main => matches!(op, Op::Ret { .. }),
268        };
269
270        match b.instructions.last() {
271            Some(last) if is_terminator(&last.op) => {}
272            _ => {
273                return Err(IrError::MissingTerminator {
274                    block: b.id.0,
275                    expected: expected_terminator,
276                })
277            }
278        }
279
280        // Values defined earlier in this block, in order.
281        let mut defined: HashSet<InstrId> = HashSet::new();
282        // The subset of `defined` that are loads, for the `Compare` lhs check.
283        // Ids are unique by then (a duplicate returns earlier), so membership
284        // answers what looking the id up in the block would.
285        let mut loads: HashSet<InstrId> = HashSet::new();
286        let last_index = b.instructions.len() - 1;
287
288        for (index, instr) in b.instructions.iter().enumerate() {
289            if !seen_instrs.insert(instr.id) {
290                return Err(IrError::DuplicateInstrId { id: instr.id.0 });
291            }
292
293            // Terminators of either kind may only be last.
294            if matches!(instr.op, Op::Yield { .. } | Op::Ret { .. }) && index != last_index {
295                return Err(IrError::MisplacedTerminator {
296                    block: b.id.0,
297                    instr: instr.id.0,
298                });
299            }
300
301            let tier_ok = match (&instr.op, b.kind) {
302                (
303                    Op::Load { .. } | Op::Compare { .. } | Op::Yield { .. },
304                    BlockKind::Comparison,
305                ) => true,
306                (
307                    Op::Observe { .. }
308                    | Op::FollowedBy { .. }
309                    | Op::Within { .. }
310                    | Op::Repeats { .. }
311                    | Op::StartStop { .. }
312                    | Op::Ret { .. },
313                    BlockKind::Main,
314                ) => true,
315                // And/Or are shared between the tiers.
316                (Op::And { .. } | Op::Or { .. }, _) => true,
317                _ => false,
318            };
319            if !tier_ok {
320                return Err(IrError::WrongTier {
321                    instr: instr.id.0,
322                    kind: kind_name,
323                });
324            }
325
326            // Resolve one operand: it must name a value defined earlier in this
327            // block, and no other operand anywhere may already have consumed it.
328            let mut check_value = |value: InstrId| -> Result<(), IrError> {
329                if !defined.contains(&value) {
330                    return Err(IrError::UnknownValue {
331                        instr: instr.id.0,
332                        value: value.0,
333                    });
334                }
335                if !used_values.insert(value) {
336                    return Err(IrError::MultipleUses {
337                        instr: instr.id.0,
338                        value: value.0,
339                    });
340                }
341                Ok(())
342            };
343
344            match &instr.op {
345                Op::Load { path } => {
346                    for step in &path.steps {
347                        if let PathStep::Index(n) = step {
348                            if *n > i64::MAX as u64 {
349                                return Err(IrError::PathIndexOutOfRange {
350                                    instr: instr.id.0,
351                                    index: *n,
352                                });
353                            }
354                        }
355                    }
356                }
357                Op::Compare {
358                    operator,
359                    negated,
360                    lhs,
361                    rhs,
362                } => {
363                    check_value(*lhs)?;
364                    if !loads.contains(lhs) {
365                        return Err(IrError::ExpectedLoad {
366                            instr: instr.id.0,
367                            lhs: lhs.0,
368                        });
369                    }
370                    if *operator == ComparisonOperator::Exists && *negated {
371                        return Err(IrError::NegatedExists { instr: instr.id.0 });
372                    }
373                    if let (ComparisonOperator::In, Operand::Set(items)) = (operator, rhs) {
374                        if items.is_empty() {
375                            return Err(IrError::OperandShape {
376                                instr: instr.id.0,
377                                detail: "IN takes a non-empty set",
378                            });
379                        }
380                    }
381                    let shape_ok = match (operator, rhs) {
382                        (ComparisonOperator::Exists, Operand::Absent) => true,
383                        (ComparisonOperator::Exists, _) => false,
384                        (ComparisonOperator::In, Operand::Set(_)) => true,
385                        (ComparisonOperator::In, _) => false,
386                        (_, Operand::Literal(_)) => true,
387                        (_, _) => false,
388                    };
389                    if !shape_ok {
390                        return Err(IrError::OperandShape {
391                            instr: instr.id.0,
392                            detail:
393                                "EXISTS takes no operand, IN takes a set, others take a literal",
394                        });
395                    }
396                    let finite = match rhs {
397                        Operand::Literal(lit) => literal_is_finite(lit),
398                        Operand::Set(items) => items.iter().all(literal_is_finite),
399                        Operand::Absent => true,
400                    };
401                    if !finite {
402                        return Err(IrError::NonFiniteFloat { instr: instr.id.0 });
403                    }
404                }
405                Op::And { lhs, rhs } | Op::Or { lhs, rhs } | Op::FollowedBy { lhs, rhs } => {
406                    check_value(*lhs)?;
407                    check_value(*rhs)?;
408                }
409                Op::Yield { value } | Op::Ret { value } => check_value(*value)?,
410                Op::Within { input, seconds } => {
411                    check_value(*input)?;
412                    if !seconds.is_finite() {
413                        return Err(IrError::NonFiniteFloat { instr: instr.id.0 });
414                    }
415                }
416                Op::Repeats { input, count } => {
417                    check_value(*input)?;
418                    if *count > i64::MAX as u64 {
419                        return Err(IrError::RepeatsOutOfRange { count: *count });
420                    }
421                }
422                Op::StartStop { input, .. } => check_value(*input)?,
423                Op::Observe { block } => {
424                    if !comparison_blocks.contains(block) {
425                        return Err(IrError::UnknownBlock {
426                            instr: instr.id.0,
427                            block: block.0,
428                        });
429                    }
430                    if !observed_blocks.insert(*block) {
431                        return Err(IrError::BlockObservedTwice { block: block.0 });
432                    }
433                }
434            }
435
436            if matches!(instr.op, Op::Load { .. }) {
437                loads.insert(instr.id);
438            }
439            defined.insert(instr.id);
440        }
441        Ok(())
442    }
443}
444
445#[cfg(test)]
446mod tests {
447    use super::*;
448    use crate::ir::{lower, BlockKind, InstrId, Instruction, Op, Operand, Program};
449    use crate::parse;
450
451    fn valid() -> Program {
452        lower(&parse("[file:size > 1024]").unwrap())
453    }
454
455    #[test]
456    fn accepts_every_lowered_corpus_pattern() {
457        let raw = include_str!("../../tests/fixtures/valid_patterns.txt");
458        for line in raw.lines().map(str::trim) {
459            if line.is_empty() || line.starts_with('#') {
460                continue;
461            }
462            let prog = lower(&parse(line).expect(line));
463            assert!(prog.validate().is_ok(), "{line} -> {:?}", prog.validate());
464        }
465    }
466
467    #[test]
468    fn rejects_a_wrong_schema_version() {
469        let mut p = valid();
470        p.schema_version = 99;
471        assert!(matches!(
472            p.validate(),
473            Err(IrError::UnsupportedSchemaVersion { found: 99, .. })
474        ));
475    }
476
477    #[test]
478    fn rejects_a_dangling_reference() {
479        let mut p = valid();
480        // Point the Yield at an id that does not exist.
481        let last = p.blocks[0].instructions.len() - 1;
482        p.blocks[0].instructions[last].op = Op::Yield {
483            value: InstrId(999),
484        };
485        assert!(matches!(p.validate(), Err(IrError::UnknownValue { .. })));
486    }
487
488    #[test]
489    fn rejects_a_forward_reference() {
490        let mut p = valid();
491        // Make the Load reference the Compare that follows it.
492        let compare_id = p.blocks[0].instructions[1].id;
493        p.blocks[0].instructions[0].op = Op::And {
494            lhs: compare_id,
495            rhs: compare_id,
496        };
497        assert!(matches!(p.validate(), Err(IrError::UnknownValue { .. })));
498    }
499
500    #[test]
501    fn rejects_a_missing_terminator() {
502        let mut p = valid();
503        p.blocks[0].instructions.pop();
504        assert!(matches!(
505            p.validate(),
506            Err(IrError::MissingTerminator { .. })
507        ));
508    }
509
510    #[test]
511    fn rejects_a_misplaced_terminator() {
512        let mut p = valid();
513        let first_id = p.blocks[0].instructions[0].id;
514        p.blocks[0].instructions.insert(
515            1,
516            Instruction {
517                id: InstrId(500),
518                op: Op::Yield { value: first_id },
519                span: None,
520            },
521        );
522        assert!(matches!(
523            p.validate(),
524            Err(IrError::MisplacedTerminator { .. })
525        ));
526    }
527
528    #[test]
529    fn rejects_a_tier_violation() {
530        let mut p = valid();
531        let first_id = p.blocks[0].instructions[0].id;
532        p.blocks[0].instructions.insert(
533            1,
534            Instruction {
535                id: InstrId(501),
536                op: Op::Within {
537                    input: first_id,
538                    seconds: 1.0,
539                },
540                span: None,
541            },
542        );
543        assert!(matches!(p.validate(), Err(IrError::WrongTier { .. })));
544    }
545
546    #[test]
547    fn rejects_an_operand_shape_mismatch() {
548        let mut p = valid();
549        match &mut p.blocks[0].instructions[1].op {
550            Op::Compare { rhs, .. } => *rhs = Operand::Absent,
551            other => panic!("expected a compare, got {other:?}"),
552        }
553        assert!(matches!(p.validate(), Err(IrError::OperandShape { .. })));
554    }
555
556    #[test]
557    fn rejects_a_duplicate_instruction_id() {
558        let mut p = valid();
559        let dup = p.blocks[0].instructions[0].clone();
560        p.blocks[0].instructions.insert(1, dup);
561        assert!(matches!(
562            p.validate(),
563            Err(IrError::DuplicateInstrId { .. })
564        ));
565    }
566
567    #[test]
568    fn rejects_observe_targeting_a_non_comparison_block() {
569        let mut p = valid();
570        let main_id = p.main.id;
571        p.main.instructions[0].op = Op::Observe { block: main_id };
572        assert!(matches!(p.validate(), Err(IrError::UnknownBlock { .. })));
573    }
574
575    #[test]
576    fn allows_dead_instructions() {
577        use crate::ast::{Literal, ObjectPath, PathStep};
578        use crate::error::Span;
579
580        let mut p = valid();
581        // A whole unreferenced subtree is legal: an editor mid-edit produces these.
582        // Its own operands are single-use, which is what keeps this about deadness
583        // rather than about sharing.
584        p.blocks[0].instructions.splice(
585            1..1,
586            [
587                Instruction {
588                    id: InstrId(600),
589                    op: Op::Load {
590                        path: ObjectPath {
591                            object_type: "file".to_string(),
592                            steps: vec![PathStep::Key("name".to_string())],
593                            span: Span::default(),
594                        },
595                    },
596                    span: None,
597                },
598                Instruction {
599                    id: InstrId(601),
600                    op: Op::Compare {
601                        operator: ComparisonOperator::Equal,
602                        negated: false,
603                        lhs: InstrId(600),
604                        rhs: Operand::Literal(Literal::String("dead".to_string())),
605                    },
606                    span: None,
607                },
608            ],
609        );
610        assert!(p.validate().is_ok(), "{:?}", p.validate());
611        // The dead compare's value is consumed by nothing.
612        assert_eq!(
613            p.blocks[0]
614                .instructions
615                .iter()
616                .filter(|i| matches!(i.op, Op::Compare { .. }))
617                .count(),
618            2
619        );
620    }
621
622    #[test]
623    fn rejects_a_duplicate_block_id() {
624        let mut p = valid();
625        let dup = p.blocks[0].clone();
626        p.blocks.push(dup);
627        assert!(matches!(
628            p.validate(),
629            Err(IrError::DuplicateBlockId { .. })
630        ));
631    }
632
633    #[test]
634    fn rejects_a_block_observed_twice() {
635        let mut p = lower(&parse("[file:size > 1] AND [file:size > 2]").unwrap());
636        let first = p.blocks[0].id;
637        let mut seen = 0;
638        for i in &mut p.main.instructions {
639            if let Op::Observe { block } = &mut i.op {
640                *block = first;
641                seen += 1;
642            }
643        }
644        assert_eq!(seen, 2);
645        assert_eq!(
646            p.validate(),
647            Err(IrError::BlockObservedTwice { block: first.0 })
648        );
649    }
650
651    #[test]
652    fn rejects_a_value_used_twice() {
653        let mut p = valid();
654        // The load is already consumed by the compare; make the yield take it too.
655        let load_id = p.blocks[0].instructions[0].id;
656        let last = p.blocks[0].instructions.len() - 1;
657        p.blocks[0].instructions[last].op = Op::Yield { value: load_id };
658        assert!(
659            matches!(p.validate(), Err(IrError::MultipleUses { value: 0, .. })),
660            "{:?}",
661            p.validate()
662        );
663    }
664
665    /// A program whose `main` block chains `levels` qualifiers onto one observation.
666    fn qualifier_chain(levels: u32) -> Program {
667        let mut p = valid();
668        let observe = p.main.instructions[0].clone();
669        let mut instrs = vec![observe.clone()];
670        let mut acc = observe.id;
671        let mut next = 1000u32;
672        for _ in 0..levels {
673            let id = InstrId(next);
674            next += 1;
675            instrs.push(Instruction {
676                id,
677                op: Op::Within {
678                    input: acc,
679                    seconds: 1.0,
680                },
681                span: None,
682            });
683            acc = id;
684        }
685        instrs.push(Instruction {
686            id: InstrId(next),
687            op: Op::Ret { value: acc },
688            span: None,
689        });
690        p.main.instructions = instrs;
691        p
692    }
693
694    #[test]
695    fn accepts_a_program_nested_past_the_old_depth_limit() {
696        // 257 levels deep: one past the 256-level limit removed by issue #32.
697        let p = qualifier_chain(255);
698        assert_eq!(p.validate(), Ok(()));
699    }
700
701    #[test]
702    fn accepts_a_very_deeply_nested_program_on_a_small_stack() {
703        // Validation is iterative, so depth costs nothing on the stack.
704        std::thread::Builder::new()
705            .stack_size(256 * 1024)
706            .spawn(|| {
707                let p = qualifier_chain(10_000);
708                assert_eq!(p.validate(), Ok(()));
709            })
710            .expect("spawn test thread")
711            .join()
712            .expect("test thread panicked");
713    }
714
715    #[test]
716    fn rejects_an_empty_in_set() {
717        let mut p = lower(&parse("[ipv4-addr:value IN ('1.1.1.1')]").unwrap());
718        match &mut p.blocks[0].instructions[1].op {
719            Op::Compare { rhs, .. } => *rhs = Operand::Set(Vec::new()),
720            other => panic!("expected a compare, got {other:?}"),
721        }
722        assert!(
723            matches!(p.validate(), Err(IrError::OperandShape { .. })),
724            "{:?}",
725            p.validate()
726        );
727    }
728
729    #[test]
730    fn rejects_a_compare_whose_lhs_is_not_a_load() {
731        use crate::ast::Literal;
732
733        let mut p = valid();
734        let compare_id = p.blocks[0].instructions[1].id;
735        let chained = InstrId(700);
736        p.blocks[0].instructions.insert(
737            2,
738            Instruction {
739                id: chained,
740                op: Op::Compare {
741                    operator: ComparisonOperator::GreaterThan,
742                    negated: false,
743                    lhs: compare_id,
744                    rhs: Operand::Literal(Literal::Integer(2)),
745                },
746                span: None,
747            },
748        );
749        // Keep every value single-use: the yield now takes the chained compare.
750        let last = p.blocks[0].instructions.len() - 1;
751        p.blocks[0].instructions[last].op = Op::Yield { value: chained };
752        assert!(
753            matches!(p.validate(), Err(IrError::ExpectedLoad { instr: 700, .. })),
754            "{:?}",
755            p.validate()
756        );
757    }
758
759    #[test]
760    fn rejects_a_negated_exists() {
761        let mut p = lower(&parse("[EXISTS file:name]").unwrap());
762        match &mut p.blocks[0].instructions[1].op {
763            Op::Compare { negated, .. } => *negated = true,
764            other => panic!("expected a compare, got {other:?}"),
765        }
766        assert!(
767            matches!(p.validate(), Err(IrError::NegatedExists { .. })),
768            "{:?}",
769            p.validate()
770        );
771    }
772
773    #[test]
774    fn rejects_a_main_block_of_the_wrong_kind() {
775        let mut p = valid();
776        p.main.kind = BlockKind::Comparison;
777        assert!(
778            matches!(p.validate(), Err(IrError::WrongBlockKind { .. })),
779            "{:?}",
780            p.validate()
781        );
782    }
783
784    #[test]
785    fn rejects_a_comparison_block_of_the_wrong_kind() {
786        let mut p = valid();
787        p.blocks[0].kind = BlockKind::Main;
788        assert!(
789            matches!(p.validate(), Err(IrError::WrongBlockKind { .. })),
790            "{:?}",
791            p.validate()
792        );
793    }
794
795    #[test]
796    fn rejects_non_finite_floats() {
797        use crate::ast::Literal;
798
799        // In a comparison operand.
800        let mut p = valid();
801        match &mut p.blocks[0].instructions[1].op {
802            Op::Compare { rhs, .. } => *rhs = Operand::Literal(Literal::Float(f64::NAN)),
803            other => panic!("expected a compare, got {other:?}"),
804        }
805        assert!(matches!(p.validate(), Err(IrError::NonFiniteFloat { .. })));
806
807        // In a WITHIN window.
808        let mut p = lower(&parse("[file:name='a'] WITHIN 60 SECONDS").unwrap());
809        for instr in &mut p.main.instructions {
810            if let Op::Within { seconds, .. } = &mut instr.op {
811                *seconds = f64::INFINITY;
812            }
813        }
814        assert!(matches!(p.validate(), Err(IrError::NonFiniteFloat { .. })));
815    }
816
817    /// A `Repeats` program over `[file:name='a']` with the given count.
818    fn repeats_program(count: u64) -> Program {
819        let mut p = lower(&parse("[file:name='a'] REPEATS 2 TIMES").unwrap());
820        for instr in &mut p.main.instructions {
821            if let Op::Repeats { count: c, .. } = &mut instr.op {
822                *c = count;
823            }
824        }
825        p
826    }
827
828    #[test]
829    fn accepts_the_largest_readable_repeats_count_and_round_trips() {
830        let p = repeats_program(i64::MAX as u64);
831        assert_eq!(p.validate(), Ok(()));
832        let text = crate::ir::render(&p);
833        assert!(parse(&text).is_ok(), "{text}");
834    }
835
836    #[test]
837    fn accepts_zero_repeats_count_the_grammar_accepts() {
838        let p = repeats_program(0);
839        assert_eq!(p.validate(), Ok(()));
840        assert!(parse(&crate::ir::render(&p)).is_ok());
841    }
842
843    #[test]
844    fn rejects_repeats_counts_the_lexer_cannot_read() {
845        for count in [i64::MAX as u64 + 1, u64::MAX] {
846            assert_eq!(
847                repeats_program(count).validate(),
848                Err(IrError::RepeatsOutOfRange { count })
849            );
850        }
851    }
852
853    /// A program whose comparison block loads a path ending in `Index(index)`.
854    fn index_program(index: u64) -> Program {
855        let mut p = valid();
856        for instr in &mut p.blocks[0].instructions {
857            if let Op::Load { path } = &mut instr.op {
858                path.steps.push(PathStep::Index(index));
859            }
860        }
861        p
862    }
863
864    #[test]
865    fn accepts_the_largest_readable_path_index_and_round_trips() {
866        let p = index_program(i64::MAX as u64);
867        assert_eq!(p.validate(), Ok(()));
868        let text = crate::ir::render(&p);
869        assert!(parse(&text).is_ok(), "{text}");
870    }
871
872    #[test]
873    fn rejects_path_indices_the_lexer_cannot_read() {
874        for index in [i64::MAX as u64 + 1, u64::MAX] {
875            assert!(
876                matches!(
877                    index_program(index).validate(),
878                    Err(IrError::PathIndexOutOfRange { index: i, .. }) if i == index
879                ),
880                "{index}"
881            );
882        }
883    }
884
885    /// Deterministic xorshift64 generator.
886    struct Rng(u64);
887    impl Rng {
888        fn next(&mut self) -> u64 {
889            self.0 ^= self.0 << 13;
890            self.0 ^= self.0 >> 7;
891            self.0 ^= self.0 << 17;
892            self.0
893        }
894    }
895
896    #[test]
897    fn validated_programs_always_render_to_parseable_text() {
898        let mut rng = Rng(0x9E37_79B9_7F4A_7C15);
899        let edge_counts = [
900            0,
901            1,
902            i64::MAX as u64 - 1,
903            i64::MAX as u64,
904            i64::MAX as u64 + 1,
905            u64::MAX,
906        ];
907        let edge_secs = [
908            0.0,
909            -0.0,
910            1.0,
911            -1.5,
912            0.1,
913            1e300,
914            -1e300,
915            f64::MAX,
916            f64::MIN,
917            f64::MIN_POSITIVE,
918            5e-324,
919            9.3e18,
920            -9.3e18,
921        ];
922        let mut validated = 0;
923        for _ in 0..600 {
924            let mut p = lower(&parse("[file:name='a']").unwrap());
925            let n_idx = rng.next() % 3;
926            for _ in 0..n_idx {
927                let index = match rng.next() % 3 {
928                    0 => edge_counts[(rng.next() % 6) as usize],
929                    1 => rng.next(),
930                    _ => rng.next() >> 1,
931                };
932                for instr in &mut p.blocks[0].instructions {
933                    if let Op::Load { path } = &mut instr.op {
934                        path.steps.push(PathStep::Index(index));
935                    }
936                }
937            }
938            let mut acc = p.main.instructions[0].id;
939            p.main.instructions.pop(); // drop the Ret; re-added below
940            let mut next = 1000u32;
941            for _ in 0..(1 + rng.next() % 3) {
942                let id = InstrId(next);
943                next += 1;
944                let op = if rng.next().is_multiple_of(2) {
945                    let count = match rng.next() % 3 {
946                        0 => edge_counts[(rng.next() % 6) as usize],
947                        1 => rng.next(),
948                        _ => rng.next() >> 1,
949                    };
950                    Op::Repeats { input: acc, count }
951                } else {
952                    let seconds = match rng.next() % 3 {
953                        0 => edge_secs[(rng.next() % edge_secs.len() as u64) as usize],
954                        1 => f64::from_bits(rng.next()),
955                        _ => (rng.next() % 100_000) as f64 / 7.0,
956                    };
957                    Op::Within {
958                        input: acc,
959                        seconds,
960                    }
961                };
962                p.main.instructions.push(Instruction { id, op, span: None });
963                acc = id;
964            }
965            p.main.instructions.push(Instruction {
966                id: InstrId(next),
967                op: Op::Ret { value: acc },
968                span: None,
969            });
970            if p.validate().is_ok() {
971                validated += 1;
972                let text = crate::ir::render(&p);
973                assert!(
974                    parse(&text).is_ok(),
975                    "validated program failed to reparse: {text}"
976                );
977            }
978        }
979        assert!(
980            validated > 100,
981            "generator produced too few valid programs: {validated}"
982        );
983    }
984}
stix_pattern/ir/validate.rs

stix_pattern/ir/
validate.rs
