lemon/dsl/
parse.rs

1//! DSL text → JSON `Expr` tree (a `serde_json::Value`).
2
3use std::collections::{HashMap, HashSet};
4
5use serde_json::{json, Map, Value};
6
7use super::lex::{lex, Token, TokenKind};
8use super::ops::{self, Field};
9use super::ParseError;
10
11/// Lower DSL text to a JSON `Expr` tree.
12pub fn parse(src: &str) -> Result<Value, ParseError> {
13    parse_analyzed(src).map(|a| a.tree)
14}
15
16/// A parse plus the source facts the linter needs: where every bare-identifier
17/// data-series reference sits, and which `let` bindings were never used.
18pub struct Analysis {
19    pub tree: Value,
20    /// Every `Data` reference: `(name, line, col)`, in source order. Includes
21    /// references inside `let` bindings (used or not).
22    pub data_refs: Vec<(String, usize, usize)>,
23    /// `let` bindings never substituted anywhere: `(name, line, col)`.
24    pub unused_lets: Vec<(String, usize, usize)>,
25}
26
27/// Like [`parse`], returning the [`Analysis`] side-channel as well.
28pub fn parse_analyzed(src: &str) -> Result<Analysis, ParseError> {
29    let toks = lex(src)?;
30    let mut p = Parser {
31        toks: &toks,
32        pos: 0,
33        env: HashMap::new(),
34        data_refs: Vec::new(),
35        let_defs: Vec::new(),
36        used_lets: HashSet::new(),
37    };
38    let tree = p.program()?;
39    let unused_lets = p
40        .let_defs
41        .iter()
42        .filter(|(n, _, _)| !p.used_lets.contains(n))
43        .cloned()
44        .collect();
45    Ok(Analysis {
46        tree,
47        data_refs: p.data_refs,
48        unused_lets,
49    })
50}
51
52struct Parser<'a> {
53    toks: &'a [Token],
54    pos: usize,
55    env: HashMap<String, Value>,
56    data_refs: Vec<(String, usize, usize)>,
57    let_defs: Vec<(String, usize, usize)>,
58    used_lets: HashSet<String>,
59}
60
61impl<'a> Parser<'a> {
62    fn peek(&self) -> &Token {
63        &self.toks[self.pos]
64    }
65
66    fn next(&mut self) -> Token {
67        let t = self.toks[self.pos].clone();
68        if self.pos + 1 < self.toks.len() {
69            self.pos += 1;
70        }
71        t
72    }
73
74    fn err(&self, message: impl Into<String>) -> ParseError {
75        let t = self.peek();
76        ParseError {
77            line: t.line,
78            col: t.col,
79            message: message.into(),
80        }
81    }
82
83    fn program(&mut self) -> Result<Value, ParseError> {
84        while self.peek().kind == TokenKind::Let {
85            self.next(); // `let`
86            let (name, line, col) = match self.next() {
87                Token {
88                    kind: TokenKind::Ident(n),
89                    line,
90                    col,
91                } => (n, line, col),
92                t => {
93                    return Err(ParseError {
94                        line: t.line,
95                        col: t.col,
96                        message: "expected name after `let`".into(),
97                    })
98                }
99            };
100            if self.next().kind != TokenKind::Eq {
101                return Err(self.err("expected `=` in let binding"));
102            }
103            let value = self.expr(0)?;
104            let value = promote(value).map_err(|m| self.err(m))?;
105            if self.env.contains_key(&name) {
106                return Err(ParseError {
107                    line,
108                    col,
109                    message: format!("`{name}` is already defined"),
110                });
111            }
112            self.let_defs.push((name.clone(), line, col));
113            self.env.insert(name, value);
114        }
115
116        let v = self.expr(0)?;
117        if self.peek().kind != TokenKind::Eof {
118            return Err(self.err("unexpected trailing input"));
119        }
120        if !v.is_object() {
121            return Err(self.err("a strategy must be an expression, not a bare constant"));
122        }
123        Ok(v)
124    }
125
126    fn expr(&mut self, min_bp: u8) -> Result<Value, ParseError> {
127        // prefix
128        let mut lhs = match &self.peek().kind {
129            TokenKind::Op(op) => {
130                let op = op.clone();
131                if let Some(tag) = ops::prefix_tag(&op) {
132                    self.next();
133                    let operand = self.expr(7)?; // prefix binds tight
134                    let of = promote(operand).map_err(|m| self.err(m))?;
135                    json!({ "op": tag, "of": of })
136                } else {
137                    return Err(self.err(format!("unexpected operator `{op}`")));
138                }
139            }
140            // `not` binds looser than comparisons, tighter than `and`:
141            // `not a > b` is `not (a > b)`; `not a and b` is `(not a) and b`.
142            TokenKind::Ident(s) if s == "not" => {
143                self.next();
144                let operand = self.expr(5)?;
145                let of = promote(operand).map_err(|m| self.err(m))?;
146                json!({ "op": "Not", "of": of })
147            }
148            _ => self.primary()?,
149        };
150
151        loop {
152            let op = match &self.peek().kind {
153                TokenKind::Op(s) => s.clone(),
154                TokenKind::Ident(s) if s == "and" || s == "or" => s.clone(),
155                _ => break,
156            };
157            let Some((l_bp, r_bp, tag)) = infix_binding(&op) else {
158                break;
159            };
160            if l_bp < min_bp {
161                break;
162            }
163            self.next(); // consume operator
164            let rhs = self.expr(r_bp)?;
165            let l = promote(lhs).map_err(|m| self.err(m))?;
166            let r = promote(rhs).map_err(|m| self.err(m))?;
167            lhs = json!({ "op": tag, "l": l, "r": r });
168        }
169        Ok(lhs)
170    }
171
172    fn primary(&mut self) -> Result<Value, ParseError> {
173        let t = self.next();
174        match t.kind {
175            TokenKind::Num(n) => Ok(number(n)),
176            TokenKind::Str(s) => Ok(Value::String(s)),
177            TokenKind::LParen => {
178                let v = self.expr(0)?;
179                if self.next().kind != TokenKind::RParen {
180                    return Err(self.err("expected `)`"));
181                }
182                Ok(v)
183            }
184            TokenKind::Ident(name) => {
185                if name == "true" {
186                    return Ok(Value::Bool(true));
187                }
188                if name == "false" {
189                    return Ok(Value::Bool(false));
190                }
191                if self.peek().kind == TokenKind::LParen {
192                    self.call(&name, t.line, t.col)
193                } else if let Some(bound) = self.env.get(&name) {
194                    self.used_lets.insert(name);
195                    Ok(bound.clone())
196                } else {
197                    self.data_refs.push((name.clone(), t.line, t.col));
198                    Ok(json!({ "op": "Data", "name": name }))
199                }
200            }
201            other => Err(ParseError {
202                line: t.line,
203                col: t.col,
204                message: format!("unexpected token {other:?}"),
205            }),
206        }
207    }
208
209    fn call(&mut self, name: &str, line: usize, col: usize) -> Result<Value, ParseError> {
210        let sig = ops::op_by_name(name).ok_or(ParseError {
211            line,
212            col,
213            message: format!("unknown op `{name}`"),
214        })?;
215        self.next(); // consume `(`
216
217        let mut positional: Vec<Value> = Vec::new();
218        let mut keyword: HashMap<String, Value> = HashMap::new();
219        let mut seen_keyword = false;
220
221        while self.peek().kind != TokenKind::RParen {
222            // keyword?  ident `=` value
223            if let TokenKind::Ident(k) = &self.peek().kind {
224                if self.toks[self.pos + 1].kind == TokenKind::Eq {
225                    let key = k.clone();
226                    self.next(); // ident
227                    self.next(); // `=`
228                    let val = self.arg_value()?;
229                    keyword.insert(key, val);
230                    seen_keyword = true;
231                    self.eat_comma()?;
232                    continue;
233                }
234            }
235            if seen_keyword {
236                return Err(self.err("positional argument after keyword argument"));
237            }
238            let val = self.arg_value()?;
239            positional.push(val);
240            self.eat_comma()?;
241        }
242        self.next(); // consume `)`
243
244        build(sig, positional, keyword).map_err(|m| ParseError {
245            line,
246            col,
247            message: m,
248        })
249    }
250
251    /// A single argument: `[ ... ]` list literal or a full expression.
252    fn arg_value(&mut self) -> Result<Value, ParseError> {
253        if self.peek().kind == TokenKind::LBracket {
254            self.next();
255            let mut items = Vec::new();
256            while self.peek().kind != TokenKind::RBracket {
257                items.push(self.expr(0)?);
258                if self.peek().kind == TokenKind::Comma {
259                    self.next();
260                }
261            }
262            self.next(); // `]`
263            return Ok(Value::Array(items));
264        }
265        self.expr(0)
266    }
267
268    fn eat_comma(&mut self) -> Result<(), ParseError> {
269        match self.peek().kind {
270            TokenKind::Comma => {
271                self.next();
272                Ok(())
273            }
274            TokenKind::RParen => Ok(()),
275            _ => Err(self.err("expected `,` or `)`")),
276        }
277    }
278}
279
280/// Emit an integral f64 as a JSON integer (so usize fields deserialize), else a float.
281fn number(n: f64) -> Value {
282    if n.fract() == 0.0 && n.abs() < 9.007e15 {
283        Value::from(n as i64)
284    } else {
285        Value::from(n)
286    }
287}
288
289/// A bare number used as an operand becomes a `Const`; objects pass through.
290fn promote(v: Value) -> Result<Value, String> {
291    match v {
292        Value::Number(n) => Ok(json!({ "op": "Const", "value": n })),
293        Value::Object(_) => Ok(v),
294        Value::Bool(_) => Err("a boolean cannot stand alone as an expression".into()),
295        Value::String(_) => Err("a string cannot stand alone as an expression".into()),
296        other => Err(format!("invalid expression: {other}")),
297    }
298}
299
300/// Place bound args into a JSON op object per the signature's field kinds.
301fn build(
302    sig: &ops::OpSig,
303    positional: Vec<Value>,
304    mut keyword: HashMap<String, Value>,
305) -> Result<Value, String> {
306    let mut obj = Map::new();
307    obj.insert("op".into(), Value::String(sig.tag.into()));
308
309    if positional.len() > sig.fields.len() {
310        return Err(format!(
311            "`{}` takes at most {} positional args",
312            sig.tag,
313            sig.fields.len()
314        ));
315    }
316
317    // Collect each field's value: positional by index, else keyword by name.
318    for (i, field) in sig.fields.iter().enumerate() {
319        let name = ops::field_name(field);
320        let provided = if i < positional.len() {
321            Some(positional[i].clone())
322        } else {
323            keyword.remove(name)
324        };
325        let Some(raw) = provided else {
326            // required fields must be present
327            if matches!(
328                field,
329                Field::Expr(_) | Field::Num(_) | Field::Str(_) | Field::ExprList(_)
330            ) {
331                return Err(format!("`{}` requires `{name}`", sig.tag));
332            }
333            continue;
334        };
335        obj.insert(name.into(), place(field, raw)?);
336    }
337
338    if let Some((k, _)) = keyword.into_iter().next() {
339        return Err(format!("`{}` has no field `{k}`", sig.tag));
340    }
341    Ok(Value::Object(obj))
342}
343
344fn place(field: &Field, raw: Value) -> Result<Value, String> {
345    match field {
346        Field::Expr(_) | Field::ExprOpt(_) => promote(raw),
347        Field::ExprList(n) => match raw {
348            Value::Array(items) => {
349                let mut out = Vec::new();
350                for it in items {
351                    out.push(promote(it)?);
352                }
353                Ok(Value::Array(out))
354            }
355            _ => Err(format!("`{n}` must be a list `[ ... ]`")),
356        },
357        Field::Num(n) | Field::NumOpt(n) => match raw {
358            Value::Number(_) => Ok(raw),
359            _ => Err(format!("`{n}` must be a number")),
360        },
361        Field::BoolOpt(n) => match raw {
362            Value::Bool(_) => Ok(raw),
363            _ => Err(format!("`{n}` must be true/false")),
364        },
365        Field::Str(n) | Field::StrOpt(n) => match raw {
366            Value::String(_) => Ok(raw),
367            _ => Err(format!("`{n}` must be a string")),
368        },
369        Field::StrListOpt(n) => match raw {
370            Value::Array(_) => Ok(raw),
371            _ => Err(format!("`{n}` must be a list of strings")),
372        },
373    }
374}
375
376/// (left_bp, right_bp, op_tag) for an infix operator, or None if not infix.
377fn infix_binding(op: &str) -> Option<(u8, u8, &'static str)> {
378    let level = match op {
379        "or" => 1,
380        "and" => 2,
381        ">" | "<" | ">=" | "<=" => 3,
382        "+" | "-" => 4,
383        "*" | "/" => 5,
384        _ => return None,
385    };
386    let tag = ops::binop_tag(op)?;
387    Some((level * 2, level * 2 + 1, tag))
388}
389
390#[cfg(test)]
391mod tests {
392    use super::*;
393    use serde_json::json;
394
395    fn p(src: &str) -> serde_json::Value {
396        parse(src).unwrap()
397    }
398
399    #[test]
400    fn data_leaf_and_number_call() {
401        assert_eq!(
402            p("sma(close, 2)"),
403            json!({"op":"Average","of":{"op":"Data","name":"close"},"n":2})
404        );
405    }
406
407    #[test]
408    fn keyword_argument() {
409        assert_eq!(
410            p("rank(close, ascending=false)"),
411            json!({"op":"Rank","of":{"op":"Data","name":"close"},"ascending":false})
412        );
413    }
414
415    #[test]
416    fn arity_and_unknown_keyword_errors() {
417        assert!(parse("sma(close)").is_err()); // missing n
418        assert!(parse("sma(close, 2, 3)").is_err()); // too many
419        assert!(parse("sma(close, bogus=2)").is_err()); // unknown keyword
420    }
421
422    #[test]
423    fn deserializes_into_expr() {
424        let v = p("sma(close, 2)");
425        let parsed: Result<crate::spec::Expr, _> = serde_json::from_value(v);
426        assert!(parsed.is_ok());
427    }
428
429    #[test]
430    fn comparison_with_const_promotion() {
431        assert_eq!(
432            p("close > 2"),
433            json!({"op":"Gt","l":{"op":"Data","name":"close"},"r":{"op":"Const","value":2}})
434        );
435    }
436
437    #[test]
438    fn and_or_precedence() {
439        // a and b or c  ==  (a and b) or c
440        assert_eq!(
441            p("a and b or c"),
442            json!({"op":"Or",
443                "l":{"op":"And","l":{"op":"Data","name":"a"},"r":{"op":"Data","name":"b"}},
444                "r":{"op":"Data","name":"c"}})
445        );
446    }
447
448    #[test]
449    fn arithmetic_precedence_and_unary() {
450        // 2 * value + quality  ==  (2*value) + quality ; and  -pe  -> Neg
451        assert_eq!(
452            p("rank(-pe)"),
453            json!({"op":"Rank","of":{"op":"Neg","of":{"op":"Data","name":"pe"}}})
454        );
455        assert_eq!(
456            p("2 * x + y"),
457            json!({"op":"Add",
458                "l":{"op":"Mul","l":{"op":"Const","value":2},"r":{"op":"Data","name":"x"}},
459                "r":{"op":"Data","name":"y"}})
460        );
461    }
462
463    #[test]
464    fn not_binds_between_and_and_comparisons() {
465        // not a > b  ==  not (a > b)
466        assert_eq!(
467            p("not a > b"),
468            json!({"op":"Not","of":{"op":"Gt",
469                "l":{"op":"Data","name":"a"},"r":{"op":"Data","name":"b"}}})
470        );
471        // not a and b  ==  (not a) and b
472        assert_eq!(
473            p("not a and b"),
474            json!({"op":"And",
475                "l":{"op":"Not","of":{"op":"Data","name":"a"}},
476                "r":{"op":"Data","name":"b"}})
477        );
478        // double negation nests
479        assert_eq!(
480            p("not not a"),
481            json!({"op":"Not","of":{"op":"Not","of":{"op":"Data","name":"a"}}})
482        );
483        // parenthesized operand
484        assert_eq!(
485            p("not (a and b)"),
486            json!({"op":"Not","of":{"op":"And",
487                "l":{"op":"Data","name":"a"},"r":{"op":"Data","name":"b"}}})
488        );
489    }
490
491    #[test]
492    fn let_inlines_subtree() {
493        let src = "let ma = sma(close, 2)\nhold_until(entry = close > ma, exit = close < ma, nstocks_limit = 1)";
494        assert_eq!(
495            p(src),
496            json!({
497                "op":"HoldUntil",
498                "entry":{"op":"Gt","l":{"op":"Data","name":"close"},
499                         "r":{"op":"Average","of":{"op":"Data","name":"close"},"n":2}},
500                "exit":{"op":"Lt","l":{"op":"Data","name":"close"},
501                        "r":{"op":"Average","of":{"op":"Data","name":"close"},"n":2}},
502                "nstocks_limit":1
503            })
504        );
505    }
506
507    #[test]
508    fn exit_when_and_quantile_row_surface() {
509        assert_eq!(
510            p("exit_when(close > sma(close, 20), close < sma(close, 60))"),
511            json!({
512                "op":"ExitWhen",
513                "entry":{"op":"Gt","l":{"op":"Data","name":"close"},
514                         "r":{"op":"Average","of":{"op":"Data","name":"close"},"n":20}},
515                "exit":{"op":"Lt","l":{"op":"Data","name":"close"},
516                        "r":{"op":"Average","of":{"op":"Data","name":"close"},"n":60}}
517            })
518        );
519        assert_eq!(
520            p("quantile_row(roe, 0.5)"),
521            json!({"op":"QuantileRow","of":{"op":"Data","name":"roe"},"c":0.5})
522        );
523        assert_eq!(
524            p("quantile_row(of = pe, c = 0.75)"),
525            json!({"op":"QuantileRow","of":{"op":"Data","name":"pe"},"c":0.75})
526        );
527    }
528
529    #[test]
530    fn cs_preprocess_surface() {
531        assert_eq!(
532            p("winsorize(pe, 0.05, 0.95)"),
533            json!({"op":"Winsorize","of":{"op":"Data","name":"pe"},"lower":0.05,"upper":0.95})
534        );
535        assert_eq!(
536            p("zscore(roe)"),
537            json!({"op":"Zscore","of":{"op":"Data","name":"roe"}})
538        );
539        assert_eq!(
540            p("bucket(momentum, 5)"),
541            json!({"op":"Bucket","of":{"op":"Data","name":"momentum"},"n":5})
542        );
543        assert_eq!(
544            p("demean(pe)"),
545            json!({"op":"Demean","of":{"op":"Data","name":"pe"}})
546        );
547    }
548
549    #[test]
550    fn in_sector_surface() {
551        assert_eq!(
552            p(r#"in_sector(close, "Technology")"#),
553            json!({"op":"InSector","of":{"op":"Data","name":"close"},"name":"Technology"})
554        );
555        assert_eq!(
556            p(r#"mask(is_largest(roe, 10), in_sector(roe, "Energy"))"#),
557            json!({
558                "op":"Mask",
559                "of":{"op":"IsLargest","of":{"op":"Data","name":"roe"},"n":10},
560                "by":{"op":"InSector","of":{"op":"Data","name":"roe"},"name":"Energy"}
561            })
562        );
563    }
564
565    #[test]
566    fn rebinding_is_an_error() {
567        assert!(parse("let a = close\nlet a = pe\na > 1").is_err());
568    }
569
570    #[test]
571    fn reports_position_on_unclosed_paren() {
572        let err = parse("sma(close, 2").unwrap_err();
573        assert!(
574            err.message.contains("`,` or `)`") || err.message.contains(")"),
575            "{}",
576            err.message
577        );
578    }
579
580    #[test]
581    fn bare_constant_is_rejected() {
582        // Const may not stand alone (engine rule).
583        assert!(parse("42").is_err());
584    }
585
586    #[test]
587    fn unknown_op_names_the_token() {
588        let err = parse("frobnicate(close)").unwrap_err();
589        assert!(err.message.contains("frobnicate"), "{}", err.message);
590    }
591}
lemon/dsl/parse.rs

lemon/dsl/
parse.rs
