stix_pattern/ir/
render.rs

1//! Rendering: [`Program`] back to canonical STIX pattern text.
2
3use std::collections::HashSet;
4
5use crate::ast::{ComparisonOperator, Literal, ObjectPath, PathStep};
6use crate::ir::index::{BlockIndex, ProgramIndex};
7use crate::ir::{InstrId, Instruction, Op, Operand, Program};
8
9/// Render a program as canonical STIX pattern text.
10///
11/// The output is canonical rather than a reproduction of any original source:
12/// whitespace is normalized, `!=` is the canonical spelling of not-equal, and
13/// parentheses appear only where operator precedence requires them. (The
14/// grammar's other spelling, `<>`, is accepted by the lexer and rendered as
15/// `!=`.)
16///
17/// For a program lowered from [`parse`](crate::parse), reparsing this output
18/// recovers the same AST up to spans, including non-ASCII string literals:
19///
20/// ```
21/// use stix_pattern::{parse, ir};
22///
23/// let ast = parse("[file:size>1024] OR [file:name='a']").unwrap();
24/// let text = ir::render(&ir::lower(&ast));
25/// assert_eq!(text, "[file:size > 1024] OR [file:name = 'a']");
26/// assert_eq!(parse(&text).unwrap().without_spans(), ast.without_spans());
27/// ```
28///
29/// The guarantee assumes the AST came from the parser: a hand-built `Comparison`
30/// using `EXISTS` with an operand other than `Literal::Boolean(true)` — the
31/// placeholder the parser writes — loses that operand, since the IR records
32/// `EXISTS` as having none.
33///
34/// Hand-built programs that share one value between two consumers render that
35/// subexpression once per use, since pattern text has no way to name a shared
36/// value. [`Program::validate`](crate::ir::Program::validate) rejects those, so
37/// check any program that did not come from `lower` before rendering it.
38///
39/// Rendering walks the program with an explicit work stack rather than by
40/// recursion, so nesting depth is limited only by memory, never by the call
41/// stack. It also terminates on a cyclic program, which `validate` rejects, by
42/// skipping any operand that names one of its own ancestors.
43pub fn render(program: &Program) -> String {
44    let mut out = String::new();
45    // Not a well-formed program if there is no terminator, or the terminator
46    // is not `Ret`; render nothing rather than panicking.
47    if let Some(Instruction {
48        op: Op::Ret { value },
49        ..
50    }) = program.main.terminator()
51    {
52        let index = ProgramIndex::new(program);
53        Renderer::new(&index).run(*value, &mut out);
54    }
55    out
56}
57
58/// Precedence of an observation-tier op: higher binds tighter.
59fn obs_prec(op: &Op) -> u8 {
60    match op {
61        Op::FollowedBy { .. } => 1,
62        Op::Or { .. } => 2,
63        Op::And { .. } => 3,
64        Op::Within { .. } | Op::Repeats { .. } | Op::StartStop { .. } => 4,
65        _ => 5,
66    }
67}
68
69/// Precedence of a comparison-tier op: higher binds tighter.
70fn cmp_prec(op: &Op) -> u8 {
71    match op {
72        Op::Or { .. } => 1,
73        Op::And { .. } => 2,
74        _ => 3,
75    }
76}
77
78/// The two expression tiers, which the renderer walks with separate rules.
79#[derive(Clone, Copy, PartialEq, Eq, Hash)]
80enum Tier {
81    Observation,
82    Comparison,
83}
84
85/// One pending step of rendering.
86///
87/// The renderer is a loop over a stack of these rather than a recursive descent,
88/// so a deeply nested program costs heap rather than stack. Because the stack is
89/// last-in first-out, an instruction's pieces are pushed in the *reverse* of the
90/// order they are written.
91enum Work<'p> {
92    /// Write the observation-tier value `value` of `main`, parenthesized when its
93    /// operator binds more loosely than `min_prec`.
94    Observation { value: InstrId, min_prec: u8 },
95    /// Write the comparison-tier value `value` of `block`, parenthesized when its
96    /// operator binds more loosely than `min_prec`.
97    Comparison {
98        block: &'p BlockIndex<'p>,
99        value: InstrId,
100        min_prec: u8,
101    },
102    /// Write fixed text.
103    Text(&'static str),
104    /// Write computed text.
105    Owned(String),
106    /// Mark an instruction as finished, i.e. no longer on the current path.
107    Leave(Tier, InstrId),
108}
109
110/// The state of one [`render`] call.
111struct Renderer<'p> {
112    index: &'p ProgramIndex<'p>,
113    stack: Vec<Work<'p>>,
114    /// The instructions currently being written: each one's ancestors, plus
115    /// itself. An operand already on the path names one of its own ancestors,
116    /// which only a cyclic (and so invalid) program can do; it is skipped so that
117    /// rendering terminates. An acyclic program never hits this, so its output is
118    /// unaffected.
119    ///
120    /// Keyed by tier rather than block: the observation tier lives only in
121    /// `main`, and the comparison tier never leaves the one block being written.
122    on_path: HashSet<(Tier, InstrId)>,
123}
124
125impl<'p> Renderer<'p> {
126    fn new(index: &'p ProgramIndex<'p>) -> Self {
127        Renderer {
128            index,
129            stack: Vec::new(),
130            on_path: HashSet::new(),
131        }
132    }
133
134    /// Write the observation-tier expression rooted at `root`.
135    fn run(mut self, root: InstrId, out: &mut String) {
136        self.stack.push(Work::Observation {
137            value: root,
138            min_prec: 1,
139        });
140        while let Some(work) = self.stack.pop() {
141            match work {
142                Work::Observation { value, min_prec } => self.observation(value, min_prec, out),
143                Work::Comparison {
144                    block,
145                    value,
146                    min_prec,
147                } => self.comparison(block, value, min_prec, out),
148                Work::Text(text) => out.push_str(text),
149                Work::Owned(text) => out.push_str(&text),
150                Work::Leave(tier, value) => {
151                    self.on_path.remove(&(tier, value));
152                }
153            }
154        }
155    }
156
157    /// Start writing `value` at `tier`: open its parentheses if it needs them and
158    /// schedule the matching close. Returns `false`, writing nothing, when `value`
159    /// is already on the current path.
160    fn enter(
161        &mut self,
162        tier: Tier,
163        value: InstrId,
164        prec: u8,
165        min_prec: u8,
166        out: &mut String,
167    ) -> bool {
168        if !self.on_path.insert((tier, value)) {
169            return false;
170        }
171        self.stack.push(Work::Leave(tier, value));
172        if prec < min_prec {
173            out.push('(');
174            self.stack.push(Work::Text(")"));
175        }
176        true
177    }
178
179    /// Schedule `lhs`, then `sep`, then `rhs`.
180    fn binary(&mut self, lhs: Work<'p>, sep: &'static str, rhs: Work<'p>) {
181        self.stack.push(rhs);
182        self.stack.push(Work::Text(sep));
183        self.stack.push(lhs);
184    }
185
186    /// Write the observation-tier expression rooted at `value`.
187    ///
188    /// Mirrors the parser's observation-level precedence — `FOLLOWEDBY`
189    /// loosest, then `OR`, then `AND`, then postfix qualifiers, then a
190    /// `[...]` or a parenthesized group — with [`obs_prec`] standing in for
191    /// those levels. `min_prec` is the tightest precedence the surrounding
192    /// context accepts; a looser operator is parenthesized. The right operand is
193    /// rendered one level tighter than the left, which is what makes these
194    /// operators left-associative on the way out. That matches how the parser
195    /// builds chains: it reads `a OR b OR c` as one chain `(a OR b) OR c`, which
196    /// lowers to `Or(Or(a, b), c)`, while a parenthesized right operand
197    /// `a OR (b OR c)` keeps its own node.
198    ///
199    /// A change to the parser's precedence needs a matching change here, or
200    /// rendering stops round-tripping.
201    fn observation(&mut self, value: InstrId, min_prec: u8, out: &mut String) {
202        let index = self.index;
203        let Some(instr) = index.main().instruction(value) else {
204            return;
205        };
206        if !self.enter(Tier::Observation, value, obs_prec(&instr.op), min_prec, out) {
207            return;
208        }
209        let obs = |value: InstrId, min_prec: u8| Work::Observation { value, min_prec };
210        match &instr.op {
211            Op::Observe { block: target } => {
212                out.push('[');
213                self.stack.push(Work::Text("]"));
214                if let Some(cb) = index.block(*target) {
215                    if let Some(Op::Yield { value }) = cb.block().terminator().map(|t| &t.op) {
216                        self.stack.push(Work::Comparison {
217                            block: cb,
218                            value: *value,
219                            min_prec: 1,
220                        });
221                    }
222                }
223            }
224            Op::FollowedBy { lhs, rhs } => self.binary(obs(*lhs, 1), " FOLLOWEDBY ", obs(*rhs, 2)),
225            Op::Or { lhs, rhs } => self.binary(obs(*lhs, 2), " OR ", obs(*rhs, 3)),
226            Op::And { lhs, rhs } => self.binary(obs(*lhs, 3), " AND ", obs(*rhs, 4)),
227            Op::Within { input, seconds } => {
228                self.stack.push(Work::Owned(format!(
229                    " WITHIN {} SECONDS",
230                    render_seconds(*seconds)
231                )));
232                self.stack.push(obs(*input, 4));
233            }
234            Op::Repeats { input, count } => {
235                self.stack
236                    .push(Work::Owned(format!(" REPEATS {count} TIMES")));
237                self.stack.push(obs(*input, 4));
238            }
239            Op::StartStop { input, start, stop } => {
240                self.stack.push(Work::Owned(format!(
241                    " START t'{}' STOP t'{}'",
242                    escape_string(start),
243                    escape_string(stop)
244                )));
245                self.stack.push(obs(*input, 4));
246            }
247            // Not valid at this tier; skip rather than panic.
248            _ => {}
249        }
250    }
251
252    /// Write the comparison-tier expression rooted at `value`, i.e. the inside of
253    /// one `[...]`.
254    ///
255    /// Mirrors the parser's comparison-level precedence — `OR` loosest, then
256    /// `AND`, then a property test or a parenthesized group — with
257    /// [`cmp_prec`] standing in for those levels. `min_prec` and the
258    /// one-level-tighter right operand work exactly as in
259    /// [`Renderer::observation`].
260    ///
261    /// A change to the parser's precedence needs a matching change here, or
262    /// rendering stops round-tripping.
263    fn comparison(
264        &mut self,
265        block: &'p BlockIndex<'p>,
266        value: InstrId,
267        min_prec: u8,
268        out: &mut String,
269    ) {
270        let Some(instr) = block.instruction(value) else {
271            return;
272        };
273        if !self.enter(Tier::Comparison, value, cmp_prec(&instr.op), min_prec, out) {
274            return;
275        }
276        let cmp = |value: InstrId, min_prec: u8| Work::Comparison {
277            block,
278            value,
279            min_prec,
280        };
281        match &instr.op {
282            Op::Or { lhs, rhs } => self.binary(cmp(*lhs, 1), " OR ", cmp(*rhs, 2)),
283            Op::And { lhs, rhs } => self.binary(cmp(*lhs, 2), " AND ", cmp(*rhs, 3)),
284            Op::Compare {
285                operator,
286                negated,
287                lhs,
288                rhs,
289            } => render_compare(block, *operator, *negated, *lhs, rhs, out),
290            // A bare Load or a non-comparison op: nothing renderable.
291            _ => {}
292        }
293    }
294}
295
296/// Write one comparison, a leaf of the comparison tier.
297fn render_compare(
298    block: &BlockIndex<'_>,
299    operator: ComparisonOperator,
300    negated: bool,
301    lhs: InstrId,
302    rhs: &Operand,
303    out: &mut String,
304) {
305    let path = match block.instruction(lhs).map(|i| &i.op) {
306        Some(Op::Load { path }) => Some(path),
307        _ => None,
308    };
309    if operator == ComparisonOperator::Exists {
310        out.push_str("EXISTS ");
311        if let Some(p) = path {
312            out.push_str(&render_path(p));
313        }
314        return;
315    }
316    if let Some(p) = path {
317        out.push_str(&render_path(p));
318    }
319    out.push(' ');
320    if negated {
321        out.push_str("NOT ");
322    }
323    out.push_str(operator_text(operator));
324    out.push(' ');
325    match rhs {
326        Operand::Literal(lit) => out.push_str(&render_literal(lit)),
327        Operand::Set(items) => {
328            let inner: Vec<String> = items.iter().map(render_literal).collect();
329            out.push('(');
330            out.push_str(&inner.join(", "));
331            out.push(')');
332        }
333        Operand::Absent => {}
334    }
335}
336
337fn operator_text(op: ComparisonOperator) -> &'static str {
338    match op {
339        ComparisonOperator::Equal => "=",
340        ComparisonOperator::NotEqual => "!=",
341        ComparisonOperator::GreaterThan => ">",
342        ComparisonOperator::GreaterThanOrEqual => ">=",
343        ComparisonOperator::LessThan => "<",
344        ComparisonOperator::LessThanOrEqual => "<=",
345        ComparisonOperator::In => "IN",
346        ComparisonOperator::Like => "LIKE",
347        ComparisonOperator::Matches => "MATCHES",
348        ComparisonOperator::IsSubset => "ISSUBSET",
349        ComparisonOperator::IsSuperset => "ISSUPERSET",
350        // Handled by the caller, which emits the prefix form.
351        ComparisonOperator::Exists => "EXISTS",
352    }
353}
354
355/// Render an object path, quoting the key steps that require it.
356pub(crate) fn render_path(path: &ObjectPath) -> String {
357    let mut out = String::new();
358    out.push_str(&path.object_type);
359    out.push(':');
360    let mut first = true;
361    for step in &path.steps {
362        match step {
363            PathStep::Key(k) => {
364                if !first {
365                    out.push('.');
366                }
367                out.push_str(&render_key(k));
368            }
369            PathStep::Index(n) => {
370                out.push_str(&format!("[{n}]"));
371            }
372            PathStep::AnyIndex => out.push_str("[*]"),
373        }
374        first = false;
375    }
376    out
377}
378
379/// A path key, bare when it lexes as a plain identifier, quoted otherwise.
380fn render_key(key: &str) -> String {
381    let plain = !key.is_empty()
382        && key
383            .chars()
384            .next()
385            .is_some_and(|c| c.is_ascii_alphabetic() || c == '_')
386        && key.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
387        && !is_keyword(key);
388    if plain {
389        key.to_string()
390    } else {
391        format!("'{}'", escape_string(key))
392    }
393}
394
395/// Whether a bare word would lex as a keyword rather than an identifier.
396///
397/// Mirrors `lexer::keyword`, which is case-insensitive.
398fn is_keyword(word: &str) -> bool {
399    matches!(
400        word.to_ascii_uppercase().as_str(),
401        "AND"
402            | "OR"
403            | "NOT"
404            | "FOLLOWEDBY"
405            | "LIKE"
406            | "MATCHES"
407            | "IN"
408            | "ISSUBSET"
409            | "ISSUPERSET"
410            | "EXISTS"
411            | "WITHIN"
412            | "REPEATS"
413            | "SECONDS"
414            | "TIMES"
415            | "START"
416            | "STOP"
417            | "TRUE"
418            | "FALSE"
419    )
420}
421
422/// Escape a string for a single-quoted STIX literal.
423pub(crate) fn escape_string(s: &str) -> String {
424    s.replace('\\', r"\\").replace('\'', r"\'")
425}
426
427/// The shortest decimal-notation rendering that parses back to exactly `v`.
428///
429/// Neither `{}` nor `{:?}` is usable here: `{}` drops the decimal point on whole
430/// numbers, so the value reparses as an integer, and `{:?}` switches to exponent
431/// notation for extreme magnitudes, which this dialect's lexer cannot read. The
432/// search starts at one decimal place, so ordinary values are as short as
433/// expected (`60.0`, `0.001`) and only extreme ones iterate.
434///
435/// `v` must be finite; [`Program::validate`](crate::ir::Program::validate)
436/// rejects non-finite floats, which STIX pattern syntax cannot express.
437pub(crate) fn render_float(v: f64) -> String {
438    for p in 1..=1100usize {
439        let s = format!("{v:.p$}");
440        if s.parse::<f64>() == Ok(v) {
441            return s;
442        }
443    }
444    // Unreachable for finite f64; keeps the function total rather than panicking.
445    format!("{v:.1}")
446}
447
448/// Render a literal in its source form.
449pub(crate) fn render_literal(lit: &Literal) -> String {
450    match lit {
451        Literal::String(s) => format!("'{}'", escape_string(s)),
452        Literal::Integer(n) => n.to_string(),
453        Literal::Float(f) => render_float(*f),
454        Literal::Boolean(b) => b.to_string(),
455        Literal::Timestamp(s) => format!("t'{}'", escape_string(s)),
456        Literal::Binary(s) => format!("b'{}'", escape_string(s)),
457        Literal::Hex(s) => format!("h'{}'", escape_string(s)),
458    }
459}
460
461/// Render a `WITHIN` window. The parser accepts an integer or a float here, so a
462/// whole number renders without a decimal point.
463///
464/// Falls back to [`render_float`] when the value is not exactly representable as
465/// an `i64`, because `as i64` saturates rather than failing — which would
466/// silently change the number.
467pub(crate) fn render_seconds(seconds: f64) -> String {
468    if seconds.fract() == 0.0 && seconds.is_finite() {
469        let as_int = seconds as i64;
470        if as_int as f64 == seconds {
471            return format!("{as_int}");
472        }
473    }
474    render_float(seconds)
475}
476
477#[cfg(test)]
478mod tests {
479    use crate::ir::{lower, render};
480    use crate::parse;
481
482    /// Render the lowering of `src`.
483    fn round(src: &str) -> String {
484        render(&lower(&parse(src).unwrap()))
485    }
486
487    /// Assert that rendering then reparsing recovers the same AST.
488    fn assert_round_trips(src: &str) {
489        let original = parse(src).unwrap();
490        let text = render(&lower(&original));
491        let reparsed =
492            parse(&text).unwrap_or_else(|e| panic!("rendered text failed to parse: {text}\n{e}"));
493        assert_eq!(
494            reparsed.without_spans(),
495            original.without_spans(),
496            "round trip changed the AST\n  src:      {src}\n  rendered: {text}"
497        );
498    }
499
500    #[test]
501    fn renders_canonical_whitespace_and_operators() {
502        assert_eq!(round("[file:name='a']"), "[file:name = 'a']");
503        assert_eq!(round("[file:size != 1]"), "[file:size != 1]");
504    }
505
506    #[test]
507    fn renders_exists_and_in() {
508        assert_eq!(round("[EXISTS file:name]"), "[EXISTS file:name]");
509        assert_eq!(
510            round("[ipv4-addr:value IN ('1.1.1.1', '8.8.8.8')]"),
511            "[ipv4-addr:value IN ('1.1.1.1', '8.8.8.8')]"
512        );
513    }
514
515    #[test]
516    fn renders_negation_in_operator_position() {
517        assert_eq!(round("[file:name NOT = 'x']"), "[file:name NOT = 'x']");
518    }
519
520    #[test]
521    fn omits_parens_where_precedence_makes_them_redundant() {
522        assert_eq!(
523            round("[(file:name = 'a') AND file:size = 1]"),
524            "[file:name = 'a' AND file:size = 1]"
525        );
526    }
527
528    #[test]
529    fn adds_parens_where_precedence_demands_them() {
530        assert_eq!(
531            round("[(file:name = 'a' OR file:name = 'b') AND file:size = 1]"),
532            "[(file:name = 'a' OR file:name = 'b') AND file:size = 1]"
533        );
534    }
535
536    #[test]
537    fn parenthesizes_a_right_nested_same_operator() {
538        // Built via explicit parens so the AST is right-nested.
539        assert_round_trips("[file:name = 'a' OR (file:name = 'b' OR file:name = 'c')]");
540        assert_eq!(
541            round("[file:name = 'a' OR (file:name = 'b' OR file:name = 'c')]"),
542            "[file:name = 'a' OR (file:name = 'b' OR file:name = 'c')]"
543        );
544    }
545
546    #[test]
547    fn parenthesizes_a_qualified_boolean_observation() {
548        // Qualifiers bind tighter than AND, so the AND needs parens.
549        assert_round_trips("([file:name='a'] AND [file:name='b']) WITHIN 60 SECONDS");
550        assert_eq!(
551            round("([file:name='a'] AND [file:name='b']) WITHIN 60 SECONDS"),
552            "([file:name = 'a'] AND [file:name = 'b']) WITHIN 60 SECONDS"
553        );
554    }
555
556    #[test]
557    fn renders_nested_qualifiers_without_parens() {
558        assert_eq!(
559            round("[file:name='a'] REPEATS 2 TIMES WITHIN 60 SECONDS"),
560            "[file:name = 'a'] REPEATS 2 TIMES WITHIN 60 SECONDS"
561        );
562    }
563
564    #[test]
565    fn preserves_float_literals_as_floats() {
566        assert_eq!(round("[file:size > 60.0]"), "[file:size > 60.0]");
567        assert_round_trips("[file:size > 60.0]");
568    }
569
570    #[test]
571    fn renders_extreme_floats_in_decimal_notation() {
572        // The exponent-notation guarantee is asserted on the number itself in
573        // float_rendering_round_trips_every_extreme; here the property that matters
574        // is that a pattern carrying such a float survives the round trip at all.
575        assert_round_trips("[file:size > 0.0000000001]");
576        assert_round_trips("[file:size > 123456789012345680.0]");
577    }
578
579    #[test]
580    fn float_rendering_stays_short_for_ordinary_values() {
581        use super::render_float;
582        assert_eq!(render_float(60.0), "60.0");
583        assert_eq!(render_float(1.5), "1.5");
584        assert_eq!(render_float(0.001), "0.001");
585    }
586
587    #[test]
588    fn float_rendering_round_trips_every_extreme() {
589        use super::render_float;
590        for v in [
591            0.0_f64,
592            -1.0,
593            1e-10,
594            1e16,
595            1e-300,
596            f64::MAX,
597            f64::MIN_POSITIVE,
598            f64::EPSILON,
599            5e-324,
600        ] {
601            let s = render_float(v);
602            assert!(!s.contains('e'), "{v:?} rendered as {s}");
603            assert!(
604                s.contains('.'),
605                "{v:?} rendered as {s}, needs a decimal point"
606            );
607            assert_eq!(s.parse::<f64>().unwrap(), v, "{v:?} rendered as {s}");
608        }
609    }
610
611    #[test]
612    fn renders_typed_literals() {
613        assert_eq!(
614            round("[file:created = t'2020-01-01T00:00:00Z']"),
615            "[file:created = t'2020-01-01T00:00:00Z']"
616        );
617        assert_eq!(
618            round("[artifact:payload_bin = b'aGVsbG8=']"),
619            "[artifact:payload_bin = b'aGVsbG8=']"
620        );
621        assert_eq!(
622            round("[file:magic_number_hex = h'cafebabe']"),
623            "[file:magic_number_hex = h'cafebabe']"
624        );
625        assert_eq!(
626            round("[file:is_encrypted = true]"),
627            "[file:is_encrypted = true]"
628        );
629    }
630
631    #[test]
632    fn quotes_path_keys_that_need_it() {
633        assert_eq!(
634            round("[file:hashes.'SHA-256' = 'abc']"),
635            "[file:hashes.'SHA-256' = 'abc']"
636        );
637        assert_eq!(
638            round("[file:hashes.MD5 = 'abc']"),
639            "[file:hashes.MD5 = 'abc']"
640        );
641    }
642
643    #[test]
644    fn renders_index_steps() {
645        assert_eq!(
646            round("[network-traffic:protocols[0] = 'tcp']"),
647            "[network-traffic:protocols[0] = 'tcp']"
648        );
649        assert_eq!(
650            round("[x-custom:list[*] = 'y']"),
651            "[x-custom:list[*] = 'y']"
652        );
653    }
654
655    #[test]
656    fn escapes_quotes_and_backslashes_in_strings() {
657        let src = r"[file:name = 'it\'s a \\ backslash']";
658        assert_round_trips(src);
659    }
660
661    #[test]
662    fn renders_start_stop() {
663        assert_eq!(
664            round("[file:name='a'] START t'2020-01-01T00:00:00Z' STOP t'2020-01-02T00:00:00Z'"),
665            "[file:name = 'a'] START t'2020-01-01T00:00:00Z' STOP t'2020-01-02T00:00:00Z'"
666        );
667    }
668
669    #[test]
670    fn escapes_quotes_in_start_stop_timestamps() {
671        // parse_timestamp_string does no RFC3339 validation, so a quote can reach
672        // the IR and must be re-escaped on the way out.
673        assert_round_trips(
674            r"[file:name='a'] START t'2020-01-01T00:00:00Z\'x' STOP t'2020-01-02T00:00:00Z'",
675        );
676    }
677
678    #[test]
679    fn non_ascii_strings_round_trip() {
680        assert_round_trips("[file:name = 'café']");
681        assert_round_trips("[file:name = '日本語 😀 it\\'s é']");
682        assert_eq!(round("[file:name='café']"), "[file:name = 'café']");
683    }
684
685    #[test]
686    fn diamond_not_equal_renders_as_bang_equal() {
687        assert_eq!(round("[file:size<>1]"), "[file:size != 1]");
688        assert_round_trips("[file:size <> 1]");
689    }
690
691    /// Run `f` on a thread with a deliberately small stack, so a test proves that
692    /// the code under test does not recurse in proportion to program depth.
693    fn on_small_stack(f: impl FnOnce() + Send + 'static) {
694        std::thread::Builder::new()
695            .stack_size(256 * 1024)
696            .spawn(f)
697            .expect("spawn test thread")
698            .join()
699            .expect("test thread panicked");
700    }
701
702    /// Nesting far beyond what a recursive renderer survives on a small stack.
703    const DEEP: u32 = 10_000;
704
705    /// `[file:size > 1024]` with `levels` `WITHIN` qualifiers chained onto it.
706    fn qualifier_chain(levels: u32) -> crate::ir::Program {
707        use crate::ir::{InstrId, Instruction, Op};
708
709        let mut p = lower(&parse("[file:size > 1024]").unwrap());
710        let observe = p.main.instructions[0].clone();
711        let mut acc = observe.id;
712        let mut instrs = vec![observe];
713        let mut next = 1000u32;
714        for _ in 0..levels {
715            let id = InstrId(next);
716            next += 1;
717            instrs.push(Instruction {
718                id,
719                op: Op::Within {
720                    input: acc,
721                    seconds: 1.0,
722                },
723                span: None,
724            });
725            acc = id;
726        }
727        instrs.push(Instruction {
728            id: InstrId(next),
729            op: Op::Ret { value: acc },
730            span: None,
731        });
732        p.main.instructions = instrs;
733        p
734    }
735
736    /// A single observation whose comparison block chains `terms` copies of
737    /// `file:size > 1024` with `AND`, nested to the left or to the right.
738    fn comparison_and_chain(terms: u32, right_nested: bool) -> crate::ir::Program {
739        use crate::ast::{ComparisonOperator, Literal};
740        use crate::ir::{InstrId, Instruction, Op, Operand};
741
742        let mut p = lower(&parse("[file:size > 1024]").unwrap());
743        let path = match &p.blocks[0].instructions[0].op {
744            Op::Load { path } => path.clone(),
745            other => panic!("expected a load, got {other:?}"),
746        };
747        let mut next = 1000u32;
748        let mut fresh = || {
749            next += 1;
750            InstrId(next)
751        };
752        let mut instrs = Vec::new();
753        let compare = |instrs: &mut Vec<Instruction>, fresh: &mut dyn FnMut() -> InstrId| {
754            let load = fresh();
755            instrs.push(Instruction {
756                id: load,
757                op: Op::Load { path: path.clone() },
758                span: None,
759            });
760            let cmp = fresh();
761            instrs.push(Instruction {
762                id: cmp,
763                op: Op::Compare {
764                    operator: ComparisonOperator::GreaterThan,
765                    negated: false,
766                    lhs: load,
767                    rhs: Operand::Literal(Literal::Integer(1024)),
768                },
769                span: None,
770            });
771            cmp
772        };
773        let mut acc = compare(&mut instrs, &mut fresh);
774        for _ in 1..terms {
775            let term = compare(&mut instrs, &mut fresh);
776            let id = fresh();
777            let (lhs, rhs) = if right_nested {
778                (term, acc)
779            } else {
780                (acc, term)
781            };
782            instrs.push(Instruction {
783                id,
784                op: Op::And { lhs, rhs },
785                span: None,
786            });
787            acc = id;
788        }
789        instrs.push(Instruction {
790            id: fresh(),
791            op: Op::Yield { value: acc },
792            span: None,
793        });
794        p.blocks[0].instructions = instrs;
795        p
796    }
797
798    #[test]
799    fn a_deep_qualifier_chain_validates_and_renders_on_a_small_stack() {
800        on_small_stack(|| {
801            let p = qualifier_chain(DEEP);
802            assert_eq!(p.validate(), Ok(()));
803            let expected = format!(
804                "[file:size > 1024]{}",
805                " WITHIN 1 SECONDS".repeat(DEEP as usize)
806            );
807            assert_eq!(render(&p), expected);
808        });
809    }
810
811    #[test]
812    fn a_deep_left_nested_comparison_chain_renders_without_parens() {
813        on_small_stack(|| {
814            let p = comparison_and_chain(DEEP, false);
815            assert_eq!(p.validate(), Ok(()));
816            let expected = format!(
817                "[{}]",
818                vec!["file:size > 1024"; DEEP as usize].join(" AND ")
819            );
820            assert_eq!(render(&p), expected);
821        });
822    }
823
824    #[test]
825    fn a_deep_right_nested_comparison_chain_parenthesizes_every_level() {
826        on_small_stack(|| {
827            let p = comparison_and_chain(DEEP, true);
828            assert_eq!(p.validate(), Ok(()));
829            let x = "file:size > 1024";
830            let wraps = DEEP as usize - 2;
831            let expected = format!(
832                "[{}{x} AND {x}{}]",
833                format!("{x} AND (").repeat(wraps),
834                ")".repeat(wraps)
835            );
836            assert_eq!(render(&p), expected);
837        });
838    }
839
840    #[test]
841    fn a_deep_right_nested_observation_chain_parenthesizes_every_level() {
842        use crate::ir::{BlockKind, Instruction, Op};
843
844        on_small_stack(|| {
845            // Build `[a] OR ([a] OR ([a] OR ...))` by lowering one observation per
846            // term and stitching their blocks together under a right-nested OR.
847            let template = lower(&parse("[file:size > 1024]").unwrap());
848            let mut p = template.clone();
849            p.blocks.clear();
850            p.main.instructions.clear();
851            let mut next_instr = 100_000u32;
852            let mut acc = None;
853            for term in 0..DEEP {
854                let mut b = template.blocks[0].clone();
855                b.id = crate::ir::BlockId(1000 + term);
856                for instr in &mut b.instructions {
857                    let old = instr.id;
858                    instr.id = crate::ir::InstrId(next_instr + old.0);
859                    match &mut instr.op {
860                        Op::Compare { lhs, .. } => lhs.0 += next_instr,
861                        Op::Yield { value } => value.0 += next_instr,
862                        _ => {}
863                    }
864                }
865                next_instr += 10;
866                assert_eq!(b.kind, BlockKind::Comparison);
867                let observe = crate::ir::InstrId(next_instr);
868                next_instr += 10;
869                p.main.instructions.push(Instruction {
870                    id: observe,
871                    op: Op::Observe { block: b.id },
872                    span: None,
873                });
874                p.blocks.push(b);
875                acc = Some(match acc {
876                    None => observe,
877                    Some(prev) => {
878                        let or = crate::ir::InstrId(next_instr);
879                        next_instr += 10;
880                        p.main.instructions.push(Instruction {
881                            id: or,
882                            op: Op::Or {
883                                lhs: observe,
884                                rhs: prev,
885                            },
886                            span: None,
887                        });
888                        or
889                    }
890                });
891            }
892            p.main.instructions.push(Instruction {
893                id: crate::ir::InstrId(next_instr),
894                op: Op::Ret {
895                    value: acc.unwrap(),
896                },
897                span: None,
898            });
899            assert_eq!(p.validate(), Ok(()));
900            let x = "[file:size > 1024]";
901            let wraps = DEEP as usize - 2;
902            let expected = format!(
903                "{}{x} OR {x}{}",
904                format!("{x} OR (").repeat(wraps),
905                ")".repeat(wraps)
906            );
907            assert_eq!(render(&p), expected);
908        });
909    }
910
911    #[test]
912    fn a_cyclic_unvalidated_program_renders_without_hanging() {
913        use crate::ir::Op;
914
915        // An `and` that names itself: `validate` rejects this as a forward
916        // reference, but `render` must still terminate on it.
917        on_small_stack(|| {
918            let mut p = lower(&parse("[file:size > 1] AND [file:size > 2]").unwrap());
919            let and = p
920                .main
921                .instructions
922                .iter_mut()
923                .find(|i| matches!(i.op, Op::And { .. }))
924                .expect("an and");
925            let id = and.id;
926            and.op = Op::And { lhs: id, rhs: id };
927            assert!(p.validate().is_err());
928            assert_eq!(render(&p), " AND ");
929        });
930    }
931
932    #[test]
933    fn large_within_windows_survive_the_round_trip() {
934        // `as i64` saturates; a whole number beyond i64::MAX must not be rendered
935        // through the integer path.
936        assert_round_trips("[file:name='a'] WITHIN 10000000000000000000.0 SECONDS");
937        // The ordinary whole-number case still renders without a decimal point.
938        assert_eq!(
939            round("[file:name='a'] WITHIN 60 SECONDS"),
940            "[file:name = 'a'] WITHIN 60 SECONDS"
941        );
942        // A fractional window keeps its fraction.
943        assert_eq!(
944            round("[file:name='a'] WITHIN 0.5 SECONDS"),
945            "[file:name = 'a'] WITHIN 0.5 SECONDS"
946        );
947    }
948}
stix_pattern/ir/render.rs

stix_pattern/ir/
render.rs
