ddquery_core/
parser.rs

1//! Hand-written recursive-descent parser with a small Pratt loop for
2//! arithmetic precedence.
3//!
4//! The pipeline is `dispatch → recursive-descent → typed AST`. There is no
5//! parser-generator dependency: the grammar is small and stable, and a
6//! generator would add a build-time codegen step. Parsing is a pure function
7//! with no I/O. Recursion depth is bounded ([`MAX_DEPTH`]) so pathologically
8//! nested input is rejected before the stack grows.
9
10use crate::{
11    ast::{
12        ArithOp, BoolOp, ChangeKind, CheckQuery, CmpOp, CompositeExpr, Condition, Filter, FuncKind,
13        FuncParam, MetricExpr, MetricQuery, Modifier, MonitorQuery, MonitorRef, ParamValue, Scalar,
14        SearchQuery, SearchSource, Series, SloQuery, SpaceAgg, TimeAgg, Window,
15    },
16    cursor::Cursor,
17    error::ParseError,
18};
19
20/// Maximum expression/recursion depth. Anything deeper is rejected as
21/// pathological input rather than risking stack growth.
22const MAX_DEPTH: usize = 128;
23
24/// Parse a Datadog monitor query into a typed AST.
25///
26/// # Errors
27///
28/// Returns a [`ParseError`] (byte offset + reason) when the query does not
29/// match any known dialect. For a non-failing entry point that degrades to
30/// [`MonitorQuery::Unparsed`], use [`crate::parse_or_unparsed`].
31pub fn parse(query: &str) -> Result<MonitorQuery, ParseError> {
32    if query.trim().is_empty() {
33        return Err(ParseError::new(0, "empty query"));
34    }
35    let mut parser = Parser::new(query);
36    let parsed = parser.parse_query()?;
37    parser.cursor.skip_ws();
38    if !parser.cursor.is_done() {
39        return Err(parser.cursor.error("unexpected trailing input"));
40    }
41    Ok(parsed)
42}
43
44/// A char predicate for identifier and metric-name-segment characters
45/// (`[A-Za-z0-9_]`).
46fn is_ident(c: char) -> bool {
47    c.is_ascii_alphanumeric() || c == '_'
48}
49
50struct Parser<'a> {
51    cursor: Cursor<'a>,
52}
53
54impl<'a> Parser<'a> {
55    fn new(input: &'a str) -> Self {
56        Self {
57            cursor: Cursor::new(input),
58        }
59    }
60
61    /// Dispatch to a dialect parser based on the leading token.
62    fn parse_query(&mut self) -> Result<MonitorQuery, ParseError> {
63        self.cursor.skip_ws();
64        match self.cursor.peek() {
65            Some('"') => self.parse_check().map(MonitorQuery::ServiceCheck),
66            Some(c) if c.is_ascii_digit() || c == '!' || c == '(' => {
67                self.parse_composite(0).map(MonitorQuery::Composite)
68            }
69            Some(_) => {
70                let head = self.peek_ident();
71                match head.as_str() {
72                    "error_budget" => self.parse_slo().map(MonitorQuery::Slo),
73                    "logs" | "events" | "rum" | "error-tracking" => {
74                        self.parse_search().map(MonitorQuery::Search)
75                    }
76                    "avg" | "sum" | "min" | "max" | "count" | "change" | "pct_change" => {
77                        self.parse_metric().map(MonitorQuery::Metric)
78                    }
79                    "" => Err(self.cursor.error("unrecognized query")),
80                    other => Err(self
81                        .cursor
82                        .error(format!("unrecognized query head `{other}`"))),
83                }
84            }
85            None => Err(self.cursor.error("empty query")),
86        }
87    }
88
89    /// Peek the leading identifier (including `-` for `error-tracking`) without
90    /// consuming it.
91    fn peek_ident(&self) -> String {
92        let mut probe = self.cursor.clone();
93        probe.take_while(|c| is_ident(c) || c == '-').to_string()
94    }
95
96    fn check_depth(&self, depth: usize) -> Result<(), ParseError> {
97        if depth > MAX_DEPTH {
98            Err(self.cursor.error("maximum nesting depth exceeded"))
99        } else {
100            Ok(())
101        }
102    }
103
104    // ----- metric dialect ------------------------------------------------
105
106    fn parse_metric(&mut self) -> Result<MetricQuery, ParseError> {
107        let head = self.take_ident()?;
108        if let Some(kind) = ChangeKind::from_token(&head) {
109            return self.parse_change_metric(kind);
110        }
111        let time_aggregation = TimeAgg::from_token(&head).ok_or_else(|| {
112            self.cursor
113                .error(format!("invalid time aggregation `{head}`"))
114        })?;
115        self.cursor.expect("(")?;
116        let window = self.take_window()?;
117        self.cursor.expect(")")?;
118        self.cursor.expect(":")?;
119        let expr = self.parse_arith(0, 0)?;
120        let condition = self.parse_condition()?;
121        Ok(MetricQuery {
122            time_aggregation,
123            window,
124            expr,
125            condition,
126        })
127    }
128
129    /// `change(avg(last_5m),last_1h): expr op threshold`.
130    fn parse_change_metric(&mut self, kind: ChangeKind) -> Result<MetricQuery, ParseError> {
131        self.cursor.expect("(")?;
132        let inner = self.take_ident()?;
133        let inner_agg = TimeAgg::from_token(&inner).ok_or_else(|| {
134            self.cursor
135                .error(format!("invalid time aggregation `{inner}`"))
136        })?;
137        self.cursor.expect("(")?;
138        let window = self.take_window()?;
139        self.cursor.expect(")")?;
140        self.cursor.expect(",")?;
141        let shift = self.take_window()?;
142        self.cursor.expect(")")?;
143        self.cursor.expect(":")?;
144        let inner_expr = self.parse_arith(0, 0)?;
145        let condition = self.parse_condition()?;
146        let expr = MetricExpr::Change {
147            kind,
148            inner_agg,
149            shift,
150            arg: Box::new(inner_expr),
151        };
152        Ok(MetricQuery {
153            time_aggregation: inner_agg,
154            window,
155            expr,
156            condition,
157        })
158    }
159
160    /// Pratt loop: `*`/`/` bind tighter than `+`/`-`.
161    fn parse_arith(&mut self, min_bp: u8, depth: usize) -> Result<MetricExpr, ParseError> {
162        self.check_depth(depth)?;
163        let mut lhs = self.parse_term(depth)?;
164        while let Some(op) = self.peek_arith_op() {
165            let (lbp, rbp) = binding_power(op);
166            if lbp < min_bp {
167                break;
168            }
169            self.cursor.eat(op.as_token());
170            let rhs = self.parse_arith(rbp, depth + 1)?;
171            lhs = MetricExpr::Arith {
172                op,
173                lhs: Box::new(lhs),
174                rhs: Box::new(rhs),
175            };
176        }
177        Ok(lhs)
178    }
179
180    fn peek_arith_op(&self) -> Option<ArithOp> {
181        match self.cursor.peek()? {
182            '+' => Some(ArithOp::Add),
183            '-' => Some(ArithOp::Sub),
184            '*' => Some(ArithOp::Mul),
185            '/' => Some(ArithOp::Div),
186            _ => None,
187        }
188    }
189
190    fn parse_term(&mut self, depth: usize) -> Result<MetricExpr, ParseError> {
191        self.check_depth(depth)?;
192        let c = self
193            .cursor
194            .peek()
195            .ok_or_else(|| self.cursor.error("unexpected end of expression"))?;
196        if c == '(' {
197            self.cursor.expect("(")?;
198            let inner = self.parse_arith(0, depth + 1)?;
199            self.cursor.expect(")")?;
200            return Ok(inner);
201        }
202        if c.is_ascii_digit() || c == '+' || c == '-' || c == '.' {
203            return Ok(MetricExpr::Scalar(Scalar::new(self.cursor.take_number()?)));
204        }
205        let id = self.take_ident()?;
206        if let Some(func) = FuncKind::from_token(&id)
207            && self.cursor.peek() == Some('(')
208        {
209            return self.parse_function(func, depth);
210        }
211        if self.cursor.peek() == Some(':') {
212            let space_aggregation = SpaceAgg::from_token(&id).ok_or_else(|| {
213                self.cursor
214                    .error(format!("invalid space aggregation `{id}`"))
215            })?;
216            self.cursor.expect(":")?;
217            return Ok(MetricExpr::Series(self.parse_series(space_aggregation)?));
218        }
219        if self.cursor.peek() == Some('(') {
220            return self.parse_transform(id, depth);
221        }
222        Err(self
223            .cursor
224            .error(format!("expected `:` or `(` after `{id}`")))
225    }
226
227    fn parse_function(&mut self, name: FuncKind, depth: usize) -> Result<MetricExpr, ParseError> {
228        self.cursor.expect("(")?;
229        let arg = self.parse_arith(0, depth + 1)?;
230        let mut params = Vec::new();
231        while self.cursor.eat(",") {
232            params.push(self.parse_func_param()?);
233        }
234        self.cursor.expect(")")?;
235        Ok(MetricExpr::Function {
236            name,
237            arg: Box::new(arg),
238            params,
239        })
240    }
241
242    fn parse_func_param(&mut self) -> Result<FuncParam, ParseError> {
243        match self.cursor.peek() {
244            Some('\'' | '"') => Ok(FuncParam::positional(ParamValue::Str(
245                self.cursor.take_quoted()?,
246            ))),
247            Some(c) if c.is_ascii_digit() || c == '+' || c == '-' || c == '.' => Ok(
248                FuncParam::positional(ParamValue::Number(self.cursor.take_number()?)),
249            ),
250            Some(_) => {
251                let key = self.take_ident()?;
252                if self.cursor.eat("=") {
253                    Ok(FuncParam::keyword(key, self.parse_param_value()?))
254                } else {
255                    Ok(FuncParam::positional(bareword_value(&key)))
256                }
257            }
258            None => Err(self.cursor.error("expected a function parameter")),
259        }
260    }
261
262    fn parse_param_value(&mut self) -> Result<ParamValue, ParseError> {
263        match self.cursor.peek() {
264            Some('\'' | '"') => Ok(ParamValue::Str(self.cursor.take_quoted()?)),
265            Some(c) if c.is_ascii_digit() || c == '+' || c == '-' || c == '.' => {
266                Ok(ParamValue::Number(self.cursor.take_number()?))
267            }
268            Some(_) => Ok(bareword_value(&self.take_ident()?)),
269            None => Err(self.cursor.error("expected a parameter value")),
270        }
271    }
272
273    fn parse_transform(&mut self, name: String, depth: usize) -> Result<MetricExpr, ParseError> {
274        self.cursor.expect("(")?;
275        let arg = self.parse_arith(0, depth + 1)?;
276        let mut args = Vec::new();
277        while self.cursor.eat(",") {
278            args.push(Scalar::new(self.cursor.take_number()?));
279        }
280        self.cursor.expect(")")?;
281        Ok(MetricExpr::Transform {
282            name,
283            arg: Box::new(arg),
284            args,
285        })
286    }
287
288    fn parse_series(&mut self, space_aggregation: SpaceAgg) -> Result<Series, ParseError> {
289        let metric = self.take_metric_name()?;
290        let filter = if self.cursor.peek() == Some('{') {
291            self.cursor.expect("{")?;
292            let filters = self.parse_filter_list();
293            self.cursor.expect("}")?;
294            filters
295        } else {
296            Vec::new()
297        };
298        let group_by = self.parse_group_by()?;
299        let modifiers = self.parse_modifiers()?;
300        Ok(Series {
301            space_aggregation,
302            metric,
303            filter,
304            group_by,
305            modifiers,
306        })
307    }
308
309    fn parse_filter_list(&mut self) -> Vec<Filter> {
310        let mut filters = Vec::new();
311        loop {
312            self.skip_filter_seps();
313            if matches!(self.cursor.peek(), Some('}') | None) {
314                break;
315            }
316            let token = self
317                .cursor
318                .take_while(|c| c != ',' && c != '}' && !c.is_whitespace());
319            if token.is_empty() {
320                break;
321            }
322            filters.push(classify_filter(token));
323        }
324        filters
325    }
326
327    /// Commas and runs of whitespace are equivalent filter separators.
328    fn skip_filter_seps(&mut self) {
329        loop {
330            self.cursor.skip_ws();
331            if !self.cursor.eat(",") {
332                break;
333            }
334        }
335    }
336
337    fn parse_group_by(&mut self) -> Result<Vec<String>, ParseError> {
338        self.cursor.skip_ws();
339        let rest = self.cursor.rest();
340        let is_by = rest
341            .strip_prefix("by")
342            .is_some_and(|after| after.starts_with(|c: char| c.is_whitespace() || c == '{'));
343        if !is_by {
344            return Ok(Vec::new());
345        }
346        self.cursor.eat("by");
347        self.cursor.expect("{")?;
348        let mut tags = Vec::new();
349        loop {
350            self.skip_filter_seps();
351            if self.cursor.peek() == Some('}') || self.cursor.peek().is_none() {
352                break;
353            }
354            let tag = self
355                .cursor
356                .take_while(|c| c != ',' && c != '}' && !c.is_whitespace());
357            if tag.is_empty() {
358                break;
359            }
360            tags.push(tag.to_string());
361        }
362        self.cursor.expect("}")?;
363        Ok(tags)
364    }
365
366    fn parse_modifiers(&mut self) -> Result<Vec<Modifier>, ParseError> {
367        let mut modifiers = Vec::new();
368        loop {
369            self.cursor.skip_ws();
370            // A `.` immediately following the series begins a modifier. Avoid
371            // skipping whitespace so arithmetic like `a . b` is never read as
372            // a modifier (which Datadog never emits anyway).
373            if !self.cursor.rest().starts_with('.') {
374                break;
375            }
376            self.cursor.expect(".")?;
377            let name = self.take_ident()?;
378            self.cursor.expect("(")?;
379            let args = self.parse_string_args()?;
380            modifiers.push(Modifier { name, args });
381        }
382        Ok(modifiers)
383    }
384
385    // ----- search dialect ------------------------------------------------
386
387    fn parse_search(&mut self) -> Result<SearchQuery, ParseError> {
388        let source = self.take_source()?;
389        self.cursor.expect("(")?;
390        let raw_search = self.cursor.take_quoted()?;
391        self.cursor.expect(")")?;
392
393        let mut index = None;
394        let mut rollup_method = None;
395        let mut rollup_arg = None;
396        let mut group_by = Vec::new();
397        let mut last = None;
398
399        while self.cursor.eat(".") {
400            let method = self.take_ident()?;
401            self.cursor.expect("(")?;
402            let mut args = self.parse_string_args()?;
403            match method.as_str() {
404                "index" => index = args.into_iter().next().filter(|s| !s.is_empty()),
405                "rollup" => {
406                    let mut it = args.into_iter();
407                    rollup_method = it.next();
408                    rollup_arg = it.next();
409                }
410                "by" => group_by = args,
411                "last" => last = args.drain(..).next(),
412                other => {
413                    return Err(self
414                        .cursor
415                        .error(format!("unknown search method `{other}`")));
416                }
417            }
418        }
419
420        let rollup_method = rollup_method
421            .ok_or_else(|| self.cursor.error("search query missing `.rollup(...)`"))?;
422        let last = last.ok_or_else(|| self.cursor.error("search query missing `.last(...)`"))?;
423        let condition = self.parse_condition()?;
424        Ok(SearchQuery {
425            source,
426            raw_search,
427            index,
428            rollup_method,
429            rollup_arg,
430            group_by,
431            last,
432            condition,
433        })
434    }
435
436    fn take_source(&mut self) -> Result<SearchSource, ParseError> {
437        let id = self.cursor.take_while(|c| is_ident(c) || c == '-');
438        match id {
439            "logs" => Ok(SearchSource::Logs),
440            "events" => Ok(SearchSource::Events),
441            "rum" => Ok(SearchSource::Rum),
442            "error-tracking" => Ok(SearchSource::ErrorTracking),
443            other => Err(self
444                .cursor
445                .error(format!("invalid search source `{other}`"))),
446        }
447    }
448
449    // ----- service-check dialect ----------------------------------------
450
451    fn parse_check(&mut self) -> Result<CheckQuery, ParseError> {
452        let check = self.cursor.take_quoted()?;
453        let mut over = Vec::new();
454        let mut by = Vec::new();
455        let mut last = None;
456        let mut saw_count = false;
457
458        while self.cursor.eat(".") {
459            let method = self.take_ident()?;
460            self.cursor.expect("(")?;
461            match method.as_str() {
462                "over" => over = self.parse_string_args()?,
463                "by" => by = self.parse_string_args()?,
464                "last" => {
465                    let n = self.cursor.take_number()?;
466                    self.cursor.expect(")")?;
467                    last = Some(checked_u32(n).ok_or_else(|| {
468                        self.cursor
469                            .error("`.last(n)` must be a non-negative integer")
470                    })?);
471                }
472                "count_by_status" => {
473                    self.parse_string_args()?;
474                    saw_count = true;
475                }
476                other => {
477                    return Err(self.cursor.error(format!("unknown check method `{other}`")));
478                }
479            }
480        }
481
482        let last = last.ok_or_else(|| self.cursor.error("check query missing `.last(n)`"))?;
483        if !saw_count {
484            return Err(self
485                .cursor
486                .error("check query missing `.count_by_status()`"));
487        }
488        Ok(CheckQuery {
489            check,
490            over,
491            by,
492            last,
493        })
494    }
495
496    // ----- SLO dialect ---------------------------------------------------
497
498    fn parse_slo(&mut self) -> Result<SloQuery, ParseError> {
499        self.cursor.expect("error_budget")?;
500        self.cursor.expect("(")?;
501        let id = self.cursor.take_quoted()?;
502        self.cursor.expect(")")?;
503        self.cursor.expect(".")?;
504        let method = self.take_ident()?;
505        if method != "over" {
506            return Err(self
507                .cursor
508                .error(format!("expected `.over(...)`, found `.{method}`")));
509        }
510        self.cursor.expect("(")?;
511        let over = self.cursor.take_quoted()?;
512        self.cursor.expect(")")?;
513        let condition = self.parse_condition()?;
514        Ok(SloQuery {
515            id,
516            over,
517            condition,
518        })
519    }
520
521    // ----- composite dialect --------------------------------------------
522
523    fn parse_composite(&mut self, depth: usize) -> Result<CompositeExpr, ParseError> {
524        self.parse_composite_or(depth)
525    }
526
527    fn parse_composite_or(&mut self, depth: usize) -> Result<CompositeExpr, ParseError> {
528        self.check_depth(depth)?;
529        let mut lhs = self.parse_composite_and(depth)?;
530        while self.cursor.eat("||") {
531            let rhs = self.parse_composite_and(depth + 1)?;
532            lhs = CompositeExpr::Binary {
533                op: BoolOp::Or,
534                lhs: Box::new(lhs),
535                rhs: Box::new(rhs),
536            };
537        }
538        Ok(lhs)
539    }
540
541    fn parse_composite_and(&mut self, depth: usize) -> Result<CompositeExpr, ParseError> {
542        self.check_depth(depth)?;
543        let mut lhs = self.parse_composite_unary(depth)?;
544        while self.cursor.eat("&&") {
545            let rhs = self.parse_composite_unary(depth + 1)?;
546            lhs = CompositeExpr::Binary {
547                op: BoolOp::And,
548                lhs: Box::new(lhs),
549                rhs: Box::new(rhs),
550            };
551        }
552        Ok(lhs)
553    }
554
555    fn parse_composite_unary(&mut self, depth: usize) -> Result<CompositeExpr, ParseError> {
556        self.check_depth(depth)?;
557        if self.cursor.eat("!") {
558            return Ok(CompositeExpr::Not(Box::new(
559                self.parse_composite_unary(depth + 1)?,
560            )));
561        }
562        if self.cursor.eat("(") {
563            let inner = self.parse_composite_or(depth + 1)?;
564            self.cursor.expect(")")?;
565            return Ok(inner);
566        }
567        let id = self.cursor.take_while(|c| c.is_ascii_digit());
568        if id.is_empty() {
569            return Err(self.cursor.error("expected a monitor id"));
570        }
571        Ok(CompositeExpr::Ref(MonitorRef { id: id.to_string() }))
572    }
573
574    // ----- shared helpers ------------------------------------------------
575
576    fn parse_condition(&mut self) -> Result<Condition, ParseError> {
577        let operator = self.parse_cmp_op()?;
578        let critical = Scalar::new(self.cursor.take_number()?);
579        Ok(Condition {
580            operator,
581            critical,
582            critical_recovery: None,
583            warning: None,
584            warning_recovery: None,
585        })
586    }
587
588    fn parse_cmp_op(&mut self) -> Result<CmpOp, ParseError> {
589        for op in [CmpOp::Ge, CmpOp::Le, CmpOp::Eq, CmpOp::Gt, CmpOp::Lt] {
590            if self.cursor.eat(op.as_token()) {
591                return Ok(op);
592            }
593        }
594        Err(self.cursor.error("expected a comparison operator"))
595    }
596
597    /// Parse comma-separated quoted-or-bareword arguments through the closing
598    /// `)`. Assumes the opening `(` has already been consumed.
599    fn parse_string_args(&mut self) -> Result<Vec<String>, ParseError> {
600        let mut out = Vec::new();
601        if self.cursor.eat(")") {
602            return Ok(out);
603        }
604        loop {
605            self.cursor.skip_ws();
606            let value = match self.cursor.peek() {
607                Some('\'' | '"') => self.cursor.take_quoted()?,
608                _ => self
609                    .cursor
610                    .take_while(|c| c != ',' && c != ')')
611                    .trim()
612                    .to_string(),
613            };
614            out.push(value);
615            if self.cursor.eat(",") {
616                continue;
617            }
618            self.cursor.expect(")")?;
619            break;
620        }
621        Ok(out)
622    }
623
624    fn take_ident(&mut self) -> Result<String, ParseError> {
625        let id = self.cursor.take_while(is_ident);
626        if id.is_empty() {
627            Err(self.cursor.error("expected an identifier"))
628        } else {
629            Ok(id.to_string())
630        }
631    }
632
633    fn take_window(&mut self) -> Result<Window, ParseError> {
634        let raw = self.cursor.take_while(is_ident);
635        Window::parse(raw).ok_or_else(|| self.cursor.error(format!("invalid window `{raw}`")))
636    }
637
638    /// Read a dotted metric name (`a.b.c`), stopping before a `.modifier(`.
639    fn take_metric_name(&mut self) -> Result<String, ParseError> {
640        let first = self.cursor.take_while(is_ident);
641        if first.is_empty() {
642            return Err(self.cursor.error("expected a metric name"));
643        }
644        let mut name = first.to_string();
645        loop {
646            if !self.cursor.rest().starts_with('.') {
647                break;
648            }
649            // Look ahead: a `.ident(` is a modifier, not a name segment.
650            let mut probe = self.cursor.clone();
651            probe.eat(".");
652            let seg = probe.take_while(is_ident);
653            if seg.is_empty() || probe.rest().starts_with('(') {
654                break;
655            }
656            self.cursor.eat(".");
657            let committed = self.cursor.take_while(is_ident);
658            name.push('.');
659            name.push_str(committed);
660        }
661        Ok(name)
662    }
663}
664
665/// Operator binding power: `*`/`/` bind tighter than `+`/`-`.
666fn binding_power(op: ArithOp) -> (u8, u8) {
667    match op {
668        ArithOp::Add | ArithOp::Sub => (1, 2),
669        ArithOp::Mul | ArithOp::Div => (3, 4),
670    }
671}
672
673/// Classify a raw filter token into a [`Filter`].
674fn classify_filter(token: &str) -> Filter {
675    if token == "*" {
676        return Filter::All;
677    }
678    let (negated, body) = match token.strip_prefix('!') {
679        Some(rest) => (true, rest),
680        None => (false, token),
681    };
682    match body.split_once(':') {
683        Some((key, value)) => Filter::Tag {
684            negated,
685            key: key.to_string(),
686            value: value.to_string(),
687        },
688        None => Filter::Glob(token.to_string()),
689    }
690}
691
692/// Interpret a bareword parameter value (`true`/`false` → bool, else string).
693fn bareword_value(word: &str) -> ParamValue {
694    match word {
695        "true" => ParamValue::Bool(true),
696        "false" => ParamValue::Bool(false),
697        other => ParamValue::Str(other.to_string()),
698    }
699}
700
701/// Convert a parsed `f64` to a `u32` if it is a non-negative whole number.
702fn checked_u32(value: f64) -> Option<u32> {
703    if value.is_finite() && value.fract() == 0.0 && (0.0..=f64::from(u32::MAX)).contains(&value) {
704        Some(value as u32)
705    } else {
706        None
707    }
708}
ddquery_core/parser.rs

ddquery_core/
parser.rs
